Забруднене молоко
Фермер Джон, відомий якістю молока, виробленого на його фермі, організовує молочну вечірку для 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. Персони 3 і 4 не захворіють під час вечірки, однак ми повинні мати на увазі, що вони можуть захворіти після вечірки. Ми повинні вважати, що сорт молока потенційно поганий, якщо кожен, хто захворів, перед цим спробував цей сорт молока.
Молоко 1: Обидва захворілі (1 і 2) пили це молоко, перш ніж захворіли, тому це молоко повинно розглядатися як потенційно погане. А раз так, то персона 3, також випивши його, може захворіти після вечірки.
Молоко 2: Обидва захворілі пили перед цим дане молоко. Тому воно теж потенційно погане. Більше ніхто не пив це молоко, тому в найгіршому випадку 2 людини захворіють, якщо це молоко погане.
Молоко 3: Це молоко не може бути поганим, оскільки людина 1 його не пила до того як захворіти. Людина 1 випила це молоко в момент часу 4, а захворіла в момент часу 3. Підозрювати молоко 1 можна було б, тільки якщо б людина 1 випила його в момент часу 2 або раніше.
Молоко 4: Воно не може бути поганим, оскільки людина 2 не пила його взагалі, але захворіла.
Тому відповідь така: Фермер Джон повинен придбати 3 дози ліків, оскільки якщо молоко 1 погане, то 3 людини захворіють.