Çirklənmiş süd#11156

Çirklənmiş süd

1 saniyə

128 meqabayt

Asan

Fermer Con, öz fermasında istehsal olunan yüksək keyfiyyətli süd ilə fermasının hüdudlarından çox-çox uzaqlarda tanınır və özünün $n$ ən yaxşı dostu üçün süd dequstasiyası ziyafəti təşkil edir. Təəssüf ki, ziyafətdə təqdim olunan $m$ süd növündən düz biri xarab çıxıb, lakin fermer Con hansı növün xarab olduğunu bilmir! Xarab südü içən hər hansı bir şəxs, sonunda xəstələnəcək — ya ziyafətin qalan hissəsi zamanı, ya da ondan bir müddət sonra.

Sizə ziyafətin yazısı verilib, ondan kimin, hansı süd növünü və hansı vaxt içdiyi, həmçinin kimin nə vaxt xəstələndiyi məlumdur. Bu məlumat əsasında hansı süd növlərinin xarab ola biləcəyini müəyyən etmək mümkündür. Bu məlumatdan istifadə edərək, fermer Cona ziyafət zamanı və ya ondan sonra xəstələnə biləcək hər kəsi zəmanətlə müalicə etmək üçün əlində olmalı olan minimum dərman dozalarının sayını tapmağa kömək edin.

Giriş

Birinci sətirdə dörd tam ədəd $n, m, d$ n, m, d və $s (1 \leq n, m \leq 50, 1 \leq d \leq 1000, 1 \leq s \leq n)$ s~(1 \le n, m \le 50, 1 \le d \le 1000, 1 \le s \le n) verilir.

Sonrakı $d$ sətrin hər birində üç tam ədəd $p$ , $mi l k$ və $t$ yerləşir, bunlar $p$ şəxsinin $t$ anında $mi l k$ növlü südü içdiyini bildirir. $p$ dəyəri $1 \dots n$ diapazonunda, $mi l k$ dəyəri $1 \dots m$ diapazonunda, $t$ isə $1 \dots 100$ diapazonundadır. Bir şəxs eyni növ südü bir neçə dəfə içə bilər, eləcə də eyni anda bir neçə fərqli süd növü içə bilər.

Sonrakı $s$ sətrin hər birində iki tam ədəd $p$ və $t$ yerləşir, bunlar $p$ şəxsinin $t$ anında xəstələndiyini bildirir. $p$ dəyəri $1 \dots n$ diapazonunda, $t$ isə $1 \dots 100$ diapazonundadır. Hər şəxs ən çox bir dəfə xəstələnir və yalnız xəstələndiyi andan qəti şəkildə kiçik olan hansısa anda xarab südü içdiyi üçün xəstələnir.

Çıxış

Fermer Conun, ziyafət zamanı və ya ondan sonra xəstələnə biləcək hər kəsi zəmanətlə müalicə etmək üçün əlində olmalı olan minimum dərman dozalarının sayını bildirən tək bir tam ədəd çap edin.

Nümunələr

Ziyafət $3$ nəfər üçün keçirilir və $4$ süd növünü əhatə edir. $1$ -ci şəxs $3$ -cü anda, $2$ -ci şəxs isə $8$ -ci anda xəstələnir. $3$ -cü şəxs ziyafət zamanı xəstələnmir, lakin onun ziyafət bitdikdən sonra xəstələnmə ehtimalını da nəzərə almaq lazımdır.

Hansı süd növlərinin xarab ola biləcəyini müəyyən etmək üçün süd növlərini növbə ilə nəzərdən keçirək. Bir süd növü, əgər xəstələnmiş hər bir şəxs xəstələnmədən əvvəl həmin südü içibsə, potensial olaraq xarab hesab olunur.

$1$ -ci süd: Hər iki xəstələnmiş şəxs ( $1$ və $2$ ) xəstələnmədən əvvəl bu süd növünü içib, ona görə də $1$ -ci süd xarab ola bilərdi. Əgər belədirsə, $3$ -cü şəxs də bu südü içib, deməli ümumilikdə $3$ nəfər xəstələnə bilər (bu zaman $3$ -cü şəxs ziyafət bitdikdən sonra xəstələnəcək).

$2$ -ci süd: Hər iki xəstələnmiş şəxs xəstələnmədən əvvəl bu süd növünü içib, ona görə də $2$ -ci süd də xarab ola bilərdi. Bu südü başqa heç kim içməyib, ona görə də dərman ən çoxu $2$ nəfər üçün lazım olacaq.

$3$ -cü süd: Bu süd xarab ola bilməz, çünki $1$ -ci şəxs xəstələnmədən əvvəl onu içməyib. $1$ -ci şəxs $3$ -cü südü $4$ -cü anda içib, lakin $3$ -cü anda xəstələnib. $3$ -cü südün $1$ -ci şəxsin xəstələnməsinə səbəb olması üçün o, südü $3$ -cü andan əvvəl içməli idi.

$4$ -cü süd: Bu süd xarab ola bilməz, çünki $2$ -ci şəxs onu heç vaxt içməyib, lakin buna baxmayaraq xəstələnib.

Beləliklə, fermer Conun $3$ doza dərmana ehtiyacı var, çünki əgər $1$ -ci süd xarab çıxarsa, sonunda $3$ nəfərin hamısı xəstələnə bilər.

Nümunə 1