ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1652. Banking Crisis

Time limit: 1.0 second
Memory limit: 64 MB
The interbank lending market has a great influence on the functioning of all banks. This is where banks can obtain cheap short-term credits from other banks. When this market was paralyzed, many banks became unable to discharge their current liabilities. Central banks of all countries agreed upon supporting the world's financial system by granting unlimited credits to banks. However, all central banks pursued protectionist policies and undertook to credit only those banks that were registered in their own countries. Moreover, to avoid speculations, it was decided to credit “responsible” banks only, i.e., those that credited other banks in the same country. Wildcat banks found a way to obtain the required status: they bought some of the debts of local banks incurred before the day of the announcement of the plan.
Given the situation in the interbank market on that day, determine the maximal number of banks that can obtain additional liquidity from central banks. You may assume that the essential quality of every banker is greed; that is why a banker always agrees to get money today even if he may lose greater money tomorrow because of that. Every debt can only be bought as a whole.


In the first line you are given the total number n of banks in the interbank market (2 ≤ n ≤ 1000). In the following n lines the banks are described by pairs of numbers ci, vi, where ci is the code of the country (1 ≤ ci ≤ 100) and vi is the amount of the available funds of the i-th bank (0 ≤ vi ≤ 109). The next line contains the number m of active contracts in the interbank market (0 ≤ m ≤ 10000). The contracts are described in the next m lines in the following format: the number of the lending bank in the above list, the number of the debtor bank, and the amount of the contract (the amounts satisfy the restriction for the available funds). Banks may buy the debts using the available funds they have initially only, banks may not use the funds they receive after selling their debts.


Output the maximal number of banks satisfying the requirements of the economy rescue plan.


1 100000
1 200000
1 300000
2 400000
2 500000
1 2 200000
1 3 200000
2 4 500000
3 5 500000


In the sample, initially only Bank 1 is responsible. Bank 2 can buy the debt of Bank 3 to Bank 1; it has enough money for that. As a result, Bank 3 will owe 200000 to Bank 2, and Bank 2 will owe 200000 to Bank 1. Bank 1 will remain responsible because it will remain a creditor of Bank 2. In addition, Bank 5 can become responsible; it has to buy the debt of Bank 4 to Bank 2.
Problem Author: Pavel Atnashev
Problem Source: NEERC 2008, Eastern subregion quarterfinals