Contaminated Milk#11156

Contaminated Milk

1 секунда

128 мегабајти

Лесно

Farmer John, known far and wide for the high quality of the milk produced on his farm, is hosting a milk-tasting party for $n$ of his best friends. Unfortunately, exactly one of the $m$ types of milk served at the party has gone bad, but Farmer John does not know which one! Anyone who drinks the bad milk will eventually become sick, either during the remainder of the party or sometime afterward.

You are given a transcript of the party recording who drank which type of milk and at what time, as well as who became sick and when. Based on this information, you can determine which types of milk could possibly be the bad one. Using this information, help Farmer John determine the minimum number of doses of medicine he needs to have on hand to guarantee that he can cure everyone who becomes sick, either during or after the party.

Влез

The first line contains four integers $n, m, d$ n, m, d, and $s (1 \leq n, m \leq 50$ s~(1 \le n, m \le 50, $1 \leq d \leq 1000, 1 \leq s \leq n)$ 1 \le d \le 1000, 1 \le s \le n).

Each of the next $d$ lines contains three integers $p$ , $mi l k$ , and $t$ , indicating that person $p$ drank milk type $mi l k$ at time $t$ . The value of $p$ is in the range $1 \dots n$ , $mi l k$ is in the range $1 \dots m$ , and $t$ is in the range $1 \dots 100$ . A person may drink the same type of milk several times and may also drink several types of milk at the same point in time.

Each of the next $s$ lines contains two integers $p$ and $t$ , indicating that person $p$ becomes sick at time $t$ . The value of $p$ is in the range $1 \dots n$ , and $t$ is in the range $1 \dots 100$ . Each person becomes sick at most once, and only because they drank the bad milk at some strictly earlier point in time.

Излез

Print one integer — the minimum number of doses of medicine Farmer John needs to obtain in order to guarantee that he can cure everyone who becomes sick, either during or after the party.

Примери

There are $3$ people and $4$ types of milk. Person $1$ becomes sick at time $3$ , while person $2$ becomes sick at time $8$ . Person $3$ does not become sick during the party, although we must consider the possibility that they could become sick later, after the party ends.

Let us consider the milk types one by one to determine which ones could be contaminated. A milk type is potentially bad if every person who became sick drank that milk before becoming sick.

Milk $1$ : Both sick people ( $1$ and $2$ ) drank this type of milk before becoming sick, so milk $1$ could be the bad milk. If it is, person $3$ also drank it, so a total of $3$ people could become sick (with person $3$ becoming sick after the party).

Milk $2$ : Both sick people drank this type of milk before becoming sick, so milk $2$ could also be the bad milk. Nobody else drank this milk, so at most $2$ people would need to be cured.

Milk $3$ : This cannot be the bad milk because person $1$ did not drink it before becoming sick. Person $1$ drank milk $3$ at time $4$ but became sick at time $3$ . For milk $3$ to have caused person $1$ to become sick, they would have had to drink it before time $3$ .

Milk $4$ : This cannot be the bad milk because person $2$ never drank it but nevertheless became sick.

Therefore, Farmer John must obtain $3$ doses of medicine, since if milk $1$ is bad, all $3$ people could eventually become sick.

Пример 1