Sữa hỏng

Có $N$ người và $M$ loại sữa. Một trong các loại sữa đã bị hỏng — ai uống sữa hỏng sẽ bị bệnh.

Cho $D$ sự kiện uống sữa, mỗi sự kiện ghi lại người $p$ uống sữa loại $m$ tại thời điểm $t$. Cho $S$ sự kiện bệnh, mỗi sự kiện ghi lại người $p$ bị bệnh tại thời điểm $t$.

Một loại sữa có thể là sữa hỏng nếu mọi người bị bệnh đều đã uống loại sữa đó trước khi bị bệnh (tức là uống tại thời điểm $<t$ bệnh).

Với mỗi loại sữa có thể là sữa hỏng, đếm số người đã uống loại sữa đó. Hãy tìm số lượng thuốc tối thiểu cần chuẩn bị để đảm bảo chữa cho tất cả mọi người có thể bị bệnh trong trường hợp xấu nhất.

Dữ liệu vào

• Dòng đầu: bốn số nguyên $N$, $M$, $D$, $S$.
• $D$ dòng tiếp theo: ba số nguyên $p$, $m$, $t$ — người $p$ uống sữa $m$ tại thời điểm $t$.
• $S$ dòng tiếp theo: hai số nguyên $p$, $t$ — người $p$ bị bệnh tại thời điểm $t$.

Dữ liệu ra

Một số nguyên duy nhất — số thuốc cần chuẩn bị (giá trị lớn nhất trong số người uống mỗi loại sữa nghi ngờ).

Ràng buộc

• $1\le N\le 50$
• $1\le M\le 50$
• $1\le D\le 1000$
• $1\le S\le N$
• $1\le t\le 100$

Ví dụ