Contaminated Milk

Farmer John is known for the quality of the milk his farm produces. Today he is hosting a milk tasting party for $N$ of his best friends ($1 \le N \le 50$). The party features $M$ types of milk ($1 \le M \le 50$), and exactly one of them has gone bad. Farmer John does not know which one. Anyone who drinks the bad milk gets sick, either during the rest of the party or after it ends.

You are given a transcript of the party. It records who drank which milk at which time, and who got sick at which time. From this record you can work out which milk types could be the bad one. Find the minimum number of doses of medicine Farmer John needs so that he can cure everyone who gets sick, whichever milk turns out to be the bad one. People who get sick after the party ends also need a dose.

The first line contains the integers $N$, $M$, $D$, and $S$.

Each of the next $D$ lines ($1 \le D \le 1000$) contains three integers $p$, $m$, $t$, meaning that person $p$ drank milk $m$ at time $t$. Here $p$ is between $1$ and $N$, $m$ is between $1$ and $M$, and $t$ is between $1$ and $100$. A person may drink the same milk several times, and may drink several types of milk at the same time.

Each of the next $S$ lines ($1 \le S \le N$) contains two integers $p$, $t$, meaning that person $p$ got sick at time $t$. Here $p$ is between $1$ and $N$, and $t$ is between $1$ and $100$. Each person gets sick at most once, and a person gets sick only because they drank the bad milk at a time strictly earlier than $t$.

Print one integer, the minimum number of doses of medicine Farmer John needs in order to treat everyone who gets sick, both during the party and after it.

There are 3 people and 4 milk types. Person 1 gets sick at time 3 and person 2 gets sick at time 8. Person 3 does not get sick during the party, but may still get sick after it ends. Consider the milk types one at a time. A milk type can be the bad one when every person who got sick drank it before getting sick.

Milk 1: both sick people, 1 and 2, drank it before getting sick, so it can be the bad milk. Person 3 also drank it, so 3 people in total would get sick. Person 3 would get sick after the party.

Milk 2: both sick people drank it before getting sick, so it can be the bad milk as well. Nobody else drank it, so at worst 2 people would get sick.

Milk 3: person 1 did not drink it before getting sick, so it is not the bad milk. Person 1 drank it at time 4 and got sick at time 3. For milk 3 to be the cause, person 1 would have had to drink it by time 2.

Milk 4: person 2 never drank it and still got sick, so it is not the bad milk.

If milk 1 is the bad one, 3 people need treatment, so the answer is 3.