Minimizing Cash Bill Exchanges

Alice, Bob, and Cynthia are tired of the chaotic way in which they settle their debts. They have decided to minimize the number of physical cash bills exchanged when settling a debt. In particular, one person (the debtor) owes another (the creditor) an amount (A) while the third person is not directly involved with the debt. However, each person holds a set of bills in various denominations. They are allowed to exchange bills among themselves to achieve the desired net settlement provided that in the final allocation the debtor’s total cash decreases by exactly (A) and the creditor’s total cash increases by exactly (A), while the neutral person’s total remains unchanged.

More formally, there are three persons numbered 1, 2, and 3. For each person (i), you are given a list of bills (each with a positive integer denomination). Let (S_i) be the sum of the values of person (i)'s bills. A single transaction is specified by three integers: (d), (c), and (A), meaning that person (d) (the debtor) must pay person (c) (the creditor) exactly (A). In the final state after exchanging bills, the new sum held by each person should be:

[ T_i = \begin{cases} S_i - A, & \text{if } i = d, \ S_i + A, & \text{if } i = c, \ S_i, & \text{otherwise.} \end{cases} ]

Each bill is transferred as an indivisible unit. A bill that remains with its original owner is not counted as an exchange; if it is assigned to a different person, it counts as one exchange. The goal is to reassign every bill to one of the three persons so that the sum of bills for person (i) equals (T_i) and the total number of exchanged bills is minimized.

For example, consider the following scenario:

• Alice (person 1) has one \(50\) bill (\(S_1 = 50\)).
• Bob (person 2) has three \(10\) bills and ten \(1\) bills (\(S_2 = 40\)).
• Cynthia (person 3) has three \(20\) bills (\(S_3 = 60\)).

If the transaction is that Alice owes Bob \(10\) (i.e. \(d=1\), \(c=2\), \(A=10\)), then the targets become \(T_1 = 40\), \(T_2 = 50\), and \(T_3 = 60\). One sequence of exchanges achieving this with only 5 bills exchanged is as follows:

1. Alice transfers her \(50\) bill to Cynthia.
2. Cynthia transfers two \(20\) bills to Alice.
3. Cynthia transfers one \(20\) bill to Bob.
4. Bob transfers one \(10\) bill to Cynthia.

This results in only 5 bill transfers. Your task is to compute the minimum number of bill exchanges required for a given test case.

Note: It is guaranteed that a valid redistribution exists for the given input.

inputFormat

The input begins with an integer 3 (the number of persons, always 3).

Then, for each person (i = 1,2,3), there is a line in the following format:

k d1 c1 d2 c2 ... dk ck

where k is the number of distinct bill denominations the person holds. For each denomination, d(j) is the bill's value and c(j) is the count of bills of that denomination. (You should expand these into individual bills for processing.)

The next line contains an integer m (the number of transactions; in all test cases m = 1).

Then m lines follow, each containing three integers:

d c A

where d is the debtor's index, c is the creditor's index, and (A) is the amount owed.

It is guaranteed that the total amount of money remains unchanged and that a valid redistribution exists.

outputFormat

Output a single integer: the minimum number of bills that must be exchanged for the transaction to be settled.

sample

3
1 50 1
2 10 3 1 10
1 20 3
1
1 2 10

5