Забруднене молоко

Вхідні дані

Перший рядок містить чотири цілі числа: $n$ (1 \le n \le 50), $m$ (1 \le m \le 50), $d$ (1 \le d \le 1000), $s$ (1 \le s \le n).

Кожен з наступних $d$ рядків містить три цілі числа: $p$, $m$, $t$, що означає, що особа $p$ випила молоко виду $m$ в момент часу $t$. $p$ в інтервалі $1\dots n$, $m$ — $1\dots m$, $t$ — $1\dots 100$. Одна людина може пити один і той же сорт кілька разів, а також кілька сортів в один момент часу.

Кожен з наступних $s$ рядків містить два цілі числа: $p$, $t$, що означає, що особа $p$ захворіла в час $t$. $p$ — $1\dots n$, $t$ — $1\dots 100$. Кожна людина захворює не більше одного разу і тільки тому, що раніше випила зіпсоване молоко.

Вихідні дані

Виведіть одне ціле число — мінімальну кількість доз ліків, необхідну Джону, щоб гарантовано вилікувати всіх хворих під час чи після вечірки.

Приклади

Є $3$ людини і $4$ види молока. Особа $1$ захворіла в момент $3$, особа $2$ — в момент $8$. Особа $3$ не захворіла під час вечірки, але ми маємо враховувати, що вона може захворіти після завершення. Розглянемо молоко по черзі: сорт вважається потенційно поганим, якщо всі хворі пили його до захворювання.

Молоко $1$: Обидва хворі ($1$ і $2$) пили цей сорт до хвороби, тобто цей сорт може бути зіпсованим. В такому разі особа $3$ також пила його і може захворіти пізніше — у цьому випадку потрібні $3$ дози ліків.

Молоко $2$: Обидва хворі пили цей сорт. Інші його не пили, тож максимум $2$ хворих.

Молоко $3$: Не може бути зіпсованим, бо особа $1$ не пила його до хвороби ($1$ пила його в момент $4$, а захворіла в $3$). Щоб цей сорт підозрювати, його треба було пити не пізніше $2$.

Молоко $4$: Не може бути зіпсованим, бо особа $2$ взагалі цього сорту не пила, але захворіла.

Відповідь — Джону потрібно $3$ дози ліків, бо якщо молоко $1$ зіпсоване, хворітимуть $3$ людини.