405972: GYM102192 L From ICPC to ACM

You, a former International Collegiate Programming Contest player, have now become an Assistant Cost Manager of Advanced Computer Manufacturing company. There are so many different kinds of costs you should deal with, including material cost, manufacturing cost and warehouse cost. Also, the customer's demand must be fully satisfied. Moreover, the space of warehouse is limited. To make things worse, all these parameters vary with time. To resolve this matter once for all, you decide to use your algorithmic knowledge to write a program.

Specifically, you have to find an optimal operational planning for the next k months, under the following constraints: in the i-th month,

• the price of raw materials is c_i yuan per unit, and the quantity of raw materials you purchase is not limited.
• the customer's demand is d_i computers, that is, you must sell exactly d_i computers to customers this month.
• your company can manufacture at most p_i computers. Manufacturing one computer consumes one unit of raw materials plus a manufacturing cost of m_i yuan.
• you can store raw materials and computers in the warehouse for future use. According to the regulations of your company, the raw materials and computers must be placed in two different areas of the warehouse. You can store at most e_i computers to the next month. However, since the volume of raw materials is negligible, the number of raw materials you store is not limited. Storing one unit of raw materials or one computer to the next month takes R_i yuan or E_i yuan, respectively.

• you may immediately use the raw materials you purchase this month to manufacture computers, as long as the the production capacity of this month is enough; likewise, you may manufacture and sell computers in the same month. These raw materials and computers do not take up warehouse space.
• initially, there are no raw materials or computers in your company.

Your program should report whether all customer's demands can be fully satisfied, and, if so, report the minimum total cost.

The first line of input is a single integer T (1 ≤ T ≤ 200), denoting the number of test cases.

Each test case begins with a single line of integer k (2 ≤ k ≤ 50000), the number of months. The i-th of the following k lines contains four integers c_i, d_i, m_i, p_i (0 ≤ c_i, d_i, m_i, p_i ≤ 10⁴), the price of raw materials, the customer's demand, the unit manufacturing cost and the manufacturing capacity of the i-th month, respectively. The i-th of the next k - 1 lines contains three integers e_i, R_i, E_i (0 ≤ e_i ≤ 10⁸, 0 ≤ R_i, E_i ≤ 10⁴), the capacities of computer area of the warehouse, and the warehouse cost of storing a unit of raw material and a computer, between the i-th and the (i + 1)-th month, respectively.

It is guaranteed that the sum of k over all test cases does not exceed 3 × 10⁵.

For each test case, display an integer in a line, denoting the minimum total cost. If customer demands cannot be fully satisfied, display -1 instead.

2
2
10 5 3 6
15 7 2 8
2 3 2
2
0 8 0 7
0 0 0 0
0 0 0

170
-1

In the first sample test case, you may purchase 12 units of raw materials, which takes 120 yuan, and put 7 of them into the warehouse for the next month, which takes 21 yuan. Then, your company may manufacture 5 computers and sell them, which takes 15 yuan. In the second month, your company may manufacture and sell 7 computers using the raw materials in the warehouse, which takes 14 yuan. The total cost is 170 yuan, which can be proved to be optimal.

In the second sample test case, the manufacturing capacity of the first month is less than the customer's demand, so the customer's demand cannot be fully satisfied.