Latte contaminato#11156

Latte contaminato

1 secondo

128 megabyte

Facile

Il Fattore John, noto ben oltre i confini della sua fattoria per l'alta qualità del latte che vi si produce, organizza una festa di degustazione di latte per $n$ dei suoi migliori amici. Sfortunatamente, esattamente uno degli $m$ tipi di latte serviti alla festa si è rivelato guasto, ma il Fattore John non sa quale! Chiunque beva il latte guasto finirà per ammalarsi — sia durante il resto della festa, sia dopo un certo tempo dalla sua conclusione.

Vi viene fornito un resoconto della festa, dal quale si sa chi ha bevuto quale tipo di latte e in quale momento, oltre a chi si è ammalato e quando. Sulla base di queste informazioni è possibile determinare quali tipi di latte potrebbero risultare guasti. Utilizzando queste informazioni, aiutate il Fattore John a determinare il numero minimo di dosi di medicinale che deve avere a disposizione per curare con certezza tutti coloro che si ammaleranno — sia durante la festa che dopo di essa.

Input

Nella prima riga si trovano quattro numeri interi $n, m, d$ n, m, d e $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).

Ciascuna delle successive $d$ righe contiene tre numeri interi $p$ , $mi l k$ e $t$ , che indicano che la persona $p$ ha bevuto il latte di tipo $mi l k$ al momento $t$ . Il valore di $p$ è compreso nell'intervallo $1 \dots n$ , $mi l k$ — nell'intervallo $1 \dots m$ , e $t$ — nell'intervallo $1 \dots 100$ . Una persona può bere più volte lo stesso tipo di latte, e può anche bere più tipi diversi di latte nello stesso momento.

Ciascuna delle successive $s$ righe contiene due numeri interi $p$ e $t$ , che indicano che la persona $p$ si ammala al momento $t$ . Il valore di $p$ è compreso nell'intervallo $1 \dots n$ , e $t$ — nell'intervallo $1 \dots 100$ . Ogni persona si ammala al massimo una volta e solo perché ha bevuto il latte guasto in un certo momento, strettamente minore del momento in cui si è ammalata.

Output

Stampate un unico numero intero — il numero minimo di dosi di medicinale che il Fattore John deve avere per curare con certezza tutti coloro che si ammaleranno, sia durante la festa che dopo di essa.

Esempi

La festa si svolge per $3$ persone e comprende $4$ tipi di latte. La persona $1$ si ammala al momento $3$ , e la persona $2$ — al momento $8$ . La persona $3$ non si ammala durante la festa, tuttavia bisogna considerare la possibilità che possa ammalarsi più tardi, dopo la fine della festa.

Esaminiamo i tipi di latte uno per uno per determinare quali di essi potrebbero risultare guasti. Un tipo di latte è potenzialmente guasto se ogni persona ammalata ha bevuto quel latte prima di ammalarsi.

Latte $1$ : Entrambe le persone ammalate ( $1$ e $2$ ) hanno bevuto questo tipo di latte prima di ammalarsi, quindi il latte $1$ potrebbe essere guasto. Se così fosse, anche la persona $3$ ha bevuto questo latte, quindi in totale potrebbero ammalarsi $3$ persone (in questo caso la persona $3$ si ammalerebbe dopo la fine della festa).

Latte $2$ : Entrambe le persone ammalate hanno bevuto questo tipo di latte prima di ammalarsi, quindi anche il latte $2$ potrebbe essere guasto. Nessun altro ha bevuto questo latte, quindi il medicinale sarà necessario al massimo per $2$ persone.

Latte $3$ : Questo latte non può essere guasto, poiché la persona $1$ non l'ha bevuto prima di ammalarsi. La persona $1$ ha bevuto il latte $3$ al momento $4$ , ma si è ammalata al momento $3$ . Perché il latte $3$ fosse la causa della malattia della persona $1$ , questa avrebbe dovuto berlo prima del momento $3$ .

Latte $4$ : Questo latte non può essere guasto, poiché la persona $2$ non lo ha mai bevuto, ma si è comunque ammalata.

Dunque, il Fattore John deve avere $3$ dosi di medicinale, poiché se il latte guasto risultasse essere il latte $1$ , alla fine potrebbero ammalarsi tutte e $3$ le persone.

Esempio 1