El Granjero Juan, conocido ampliamente por la calidad de la leche producida en su granja, está llevando a cabo una fiesta de degustación de leche para ~N~ de sus mejores amigos ~(1 \leq N \leq 50)~. Desafortunadamente, de los ~M~ tipos de leche presentados en la fiesta ~(1 \leq M \leq 50)~, exactamente uno de ellos se ha dañado, ¡pero el Granjero Juan no sabe cuál es! Cualquiera que tome la leche dañada se enferma después, durante el resto de la fiesta o después. A usted se le da una transcripción de la fiesta -- quién toma que cuando, y también quién se enferma. Basado en esta información, usted puede deducir cuál de las leches podría ser posiblemente la dañada. Usando este conocimiento, ayude al Granjero Juan a determinar la cantidad mínima de dosis de medicina que él necesitará obtener con el propósito de garantizar que él pueda curar todos los individuos que se enfermen, durante o después de la fiesta.

Entrada

La primera línea contiene los enteros ~N, M, D~ y ~S~. Cada una de las siguientes ~D~ ~(1 \le D \le 1000)~ líneas contiene tres enteros ~p,m,t,~ indicando que la persona tomó la leche m en el tiempo ~t~. El valor de p está en el rango ~1...N~, mestá en el rango ~1...M~ y testá en el rango ~1...100~. Una persona puede tomar la misma leche varias veces y puede también tomar varias clases de leche en el mismo punto de tiempo. Cada una de las siguientes ~S~ ~(1 \leq S \leq N )~ líneas contienen dos enteros ~p,t~ indicando que la persona ~p~ se enferma en el tiempo ~t~. El valor de ~p~ está en el rango ~1...N~ y ~t~ está en el rango ~1...100~. Cada persona se enferma a lo más una vez y solamente se enferma debido a que tomó leche dañada en algún punto estrictamente anterior de tiempo.

Salida

Un solo entero, especificando el número mínimo de dosis de medicina que el Granjero Juan necesita obtener de tal manera que él pueda garantizar que tendrá suficientes dosis para darle tratamiento a la gente que se enferme, tanto durante como después de la fiesta.

Ejemplo de Entrada

3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 8

Ejemplo de Salida

 3

Explicación de la Salida

Hay 3 personas y 4 tipos de leche. La persona 1 se enferma en el tiempo 3 y la persona 2 se enferma en el tiempo 8. La persona 3 y la persona 4 no se enferman durante la fiesta, aunque aún debemos considerar la posibilidad que podrían enfermarse después, después que la fiesta termine. Consideremos los tipos de leche uno por uno para ver cual podría estar contaminada; sabemos que un tipo de leche es potencialmente mala si todos los que se enfermaron tomaron esa leche antes de enfermarse.

Leche 1: Ambos de los enfermos (1 y 2) tomaron esta leche antes de enfermarse, por lo tanto esta podría ser la leche dañada. Si es así, la persona 3 también la tomó, entonces podrían haber un total de 3 persona que se enfermaran (la persona 3 podría enfermarse después de la fiesta).

Leche 2: Ambas de las personas enfermas tomaron esta leche antes de enfermarse, entonces podría también ser la leche dañada. Nadie más tomó esta leche, entonces a lo más 2 personas podrían enfermarse si esta es la leche dañada.

Leche 3: Esta no puede ser la leche dañada debido a que la persona 1 no la tomó antes de enfermarse -- la persona 1 la tomó en el tiempo 4, y se enfermó en el tiempo 3. Para que la leche 3 implicara que la persona 1 se enfermase, la persona 1 tendría que haber tomado esta leche en el tiempo 2 a más tardar.

Leche 4: Esta no puede ser la leche dañada porque la persona 2 no la tomó, y aún así la persona 2 se enfermó.

La respuesta es por lo tanto que el Granjero Juan debe obtener 3 dosis de medicina, desde que si la leche 1 es la dañada, entonces un total de 3 personas necesitarán ser curadas.