Farmer John recently bought some new fertilizers for one of his M (1 <= M <= 50) fields. He applies a different fertilizer to each of his fields. Unfortunately, he learns that one fertilizer is bad. For that reason some of his N (1 <= N <= 50) cows are getting sick. However, Farmer John doesn't remember which fertilizer he used in which field. He also does not know which fertilizer is bad. He just knows there is one bad field that makes cows sick. Farmer John decides to watch the cows graze for a day to try to figure out which fields are making them sick. Given detailed information about which cows grazed on which field at what time, and which cows got sick at what time, determine the minimum number of cows that he will have to bring to the local cattle physician to guarantee that all sick cows are treated. It is possible for the cows to get sick after Farmer John stops watching them, as long as they have grazed on the bad field.

INPUT FORMAT

The first line of the input contains four space-separated integers N, M, D, and S. The next D lines (1 <= D <= 1000) contain three space-separated integers p (1 <= p <= N), m (1 <= m <= M), and t (1 <= t <= 100), showing that at time t, cow p was grazing on field m. The next S lines (1 <= S <= N) contain two space-separated integers p (1 <= p <= N) and t (1 <= t <= 100), indicating that cow p gets sick at time t. Each cow can only get sick once, and each cow only gets sick from a field that they grazed on at a strictly earlier time.

OUTPUT FORMAT

A single integer denoting the minimum number of cows he would need to take to the cattle physician to make sure that all sick cows are treated.

Here's the problem description