Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для \(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
|
|
2
|
6 3
2
1
1
3
2
1
1 6
3 3
2 4
|
3 2 1
1 0 0
2 0 1
|
|
3
|
4
1
8
4
3
|
2
|
|
4
|
4
1
8
4
3
|
3
|
|
5
|
4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1
|
10
|
|
6
|
8 5 6
|
8
|
|
7
|
4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3
|
2
6
3
8
|
|
8
|
3
1
6
4
|
2
|
|
9
|
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1
|
5
|
|
10
|
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
|
9
|
|
11
|
7 10
4 8
|
6
|
|
12
|
3 3
40 75
50 35
10 45
40 76
20 30
40 40
|
5
|