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
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
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