Description

Due to the massive infiltration of foreign spies, national security is in a severe crisis. If spy A holds incriminating evidence against spy B, we say that A can expose B. Some spies accept bribes; as long as they are paid a certain amount of dollars, they are willing to hand over all the intelligence they hold. Therefore, if we can buy off some spies, we may be able to control every individual in the spy network. Once we arrest a spy, all the intelligence they hold becomes ours, which may enable us to arrest new spies and acquire new intelligence.

Our counterintelligence agency has provided a dossier that includes all known bribable spies and the exact amount they demand. We also know which spies hold information about which other spies. Assume there are $n$ spies in total ($n \le 3000$), each identified by an integer from 1 to 3000.

Based on this dossier, determine whether it is possible to control all spies. If it is possible, find the minimum total payment required. Otherwise, output one spy who cannot be controlled.

Input Format

• The first line contains a single integer $n$.
• The second line contains an integer $p$, the number of spies willing to be bribed, with $1 \le p \le n$.
• The next $p$ lines each contain two integers: the ID of a bribable spy, and the amount required to bribe them. This amount does not exceed 20000.
• The next line contains a single integer $r$, with $1 \le r \le 8000$.
• The next $r$ lines each contain two positive integers, representing a pair $(A, B)$, meaning spy $A$ holds evidence against spy $B$.

Output Format

• If it is possible to control all spies, output YES on the first line, and the minimum total bribe on the second line.
• Otherwise, output NO on the first line, and on the second line output the smallest ID among the spies that cannot be controlled.

3
2
1 10
2 100
2
1 3
2 3

YES
110

4
2
1 100
4 200
2
1 2
3 4

NO
3

Hint

Translated by ChatGPT 5