Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для n своих лучших друзей. Из m сортов молока, подготовленных к вечеринке, ровно один испортился, но ФД не знает какой. Тому, кто его выпьет, станет плохо.

Вам дали протокол вечеринки - кто что и когда пил, а также кому стало плохо. Основываясь на этой информации, Вы должны определить какие сорта молока возможно плохие.

Входные данные

Первая строка ввода содержит числа n (1 ≤ n ≤ 50), m (1 ≤ m ≤ 50), d (1 ≤ d ≤ 1000), s.

Каждая из следующих d строк содержит три целых числа p, m, t, указывающих, что персона p выпила сорт молока m в момент времени t. Значение p находится в интервале 1..n, m в интервале 1..m, и t в интервале 1..100. Кажды человек может пить один и тот же сорт молока несколько раз, и может пить несколько сортов молока в один и тот же момент времени.

Каждая из следующих s (1 ≤ s ≤ n) строк содержит два целых числа p, t, указывающих, что персона p заболела в момент времени t. Значение p в интервале 1..n, а значение t в интервале 1..100. Каждый человек заболеет не более одного раза, как следствие того, что он выпил плохое молоко в какой-то строго более ранний момент времени.

Выходные данные

Одно целое число, указывающее минимальное количество доз лекарств, которое потребуется фермеру Джону, чтобы вылечить всех людей, которым станет плохо во время или после вечеринки.

Пример

Всего имеется 3 человека и 4 вида молока. Человек 1 заболеет в момент времени 3, а человек 2 заболеет в момент времени 8, а человек 2 заболеет в момент времени 8. Персоны 3 и 4 не заболеют во время вечерники, однако мы должны иметь ввиду, что они могут заболеть после вечеринки. Мы должны считать, что сорт молока потенциально плохой, если каждый, кто заболел, перед этим попробовал этот сорт молока.

Молоко 1: Оба заболевших (1 и 2) пили это молоко, прежде, чем заболели поэтому это молоко должно рассматриваться как потенциально плохое. А раз так, то персона 3 также выпивший его может заболеть после вечеринки.

Молоко 2: Оба заболевших пили перед этим данное молоко. Поэтому оно тоже потенциально плохое. Больше никто не пил это молоко, поэтому в худшем случае 2 человека заболели, если это молоко плохое.

Молоко 3: Это молоко не может быть плохим, поскольку человек 1 его не пил до того как заболеть. Человек 1 выпил этот молоко в момент времени 4, а заболел в момент времени 3. Подозревать молоко 1 можно было бы, только если бы человек 1 выпил его в момент времени 2 или раньше.

Молоко 4: Оно не может быть плохим, поскольку человек 2 не пил его вообще, но заболел.

Поэтому ответ таков: ФД должен приобрести 3 дозы лекарства, поскольку если молоко 1 плохое, то 3 человека заболеют.