Controlling the Spy Network

Due to a massive infiltration of foreign spies, our national security is at a high risk. A spy A can expose spy B if A holds incriminating evidence against B. Some spies accept bribes – if offered a certain amount in dollars, they will hand over all the intelligence they possess. Moreover, once a spy is arrested, all the intelligence in his possession becomes ours, which may lead to further arrests.

We are provided with two pieces of information:

• A list of spies who accept bribes, along with the exact dollar amount they demand.
• A list of relationships indicating which spy holds incriminating evidence against which spy.

Assume there are \( n \) spies (with \( n \le 3000 \)), identified by integers from 1 to n. By bribing some of these spies, we can start a chain reaction: once a spy is controlled (either by bribery or by subsequent arrest using the evidence collected), all evidence held by that spy becomes available, aiding in controlling more spies.

Your task is to determine if it is possible to control all spies. If it is possible, compute the minimum total amount of money required for the bribes. Otherwise, output the identifier of one spy that cannot be controlled.

inputFormat

The first line contains three integers: n, m, and k, representing the number of spies, the number of evidence relations, and the number of bribable spies, respectively.

The following m lines each contain two integers A and B. Each such line indicates that spy A holds incriminating evidence against spy B.

The next k lines each contain two integers x and c, indicating that spy x can be bribed for c dollars. If multiple bribe offers exist for the same spy, the smallest bribe is used.

outputFormat

If it is possible to control all spies, output a single integer representing the minimum total cost required. Otherwise, output the identifier (an integer) of any spy that cannot be controlled.

sample

4 4 2
1 2
2 3
3 4
4 2
1 10
3 5

10