Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для \(N\) своих лучших друзей (\(1 \leq N \leq 50\)).
Из \(M\) сортов молока, подготовленных к вечеринке , (\(1 \leq M \leq 50\)) ровно один испортился, но ФД не знает какой. Тому, кто его выпьет, станет плохо.
Вам дали протокол вечеринки - кто что и когда пил, а также кому стало плохо. Основываясь на этой информации, Вы должны определить какие сорта молока возможно плохие.
Формат входных данных:
Первая строка ввода содержит числа
\(N\),
\(M\),
\(D\),
\(S\).
Каждая из следующих \(D\) строк (\(1 \leq D \leq 1000\)) содержит три целых
числа \(p, m, t\), указывающих, что персона \(p\) выпила сорт молока \(m\) в момент времени
\(t\). Значение \(p\) находится в интервале \(1 \ldots N\), \(m\) в интервале
\(1 \ldots M\), и \(t\) в интервале \(1 \ldots 100\). Кажды человек может
пить один и тот же сорт молока несколько раз, и может пить несколько сортов
молока в один и тот же момент времени.
Каждая из следующих \(S\) строк (\(1 \leq S \leq N\)) содержит два целых числа
\(p, t\), указывающих, что персона \(p\) заболела в момент времени \(t\). Значение
\(p\) в интервале \(1 \ldots N\), а значение \(t\) в интервале $1 \ldots
100$. Каждый человек заболеет не более одного раза, как следствие того, что он
выпил плохое молоко в какой-то строго более ранний момент времени.
Формат вывода (файл
badmilk.out):
Одно целое число, указывающее минимальное количество доз лекарств,
которое потребуется фермеру Джону, чтобы вылечить всех людей, которым станет
плохо во время или после вечеринки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
3
|