6408：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: $\textbf{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.

Also,
- 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 \leq T \leq 200)$, denoting the number of test cases.

Each test case begins with a single line of integer $k$ $(2 \leq k \leq 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 \leq c_i, d_i, m_i, p_i \leq 10^4)$, 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 \leq e_i \leq 10^8, 0 \leq R_i, E_i \leq 10^4)$, 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 \times 10^5$.

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