L. From ICPC to ACM
time limit per test
2 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

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 ci yuan per unit, and the quantity of raw materials you purchase is not limited.
  • the customer's demand is di computers, that is, you must sell exactly di computers to customers this month.
  • your company can manufacture at most pi computers. Manufacturing one computer consumes one unit of raw materials plus a manufacturing cost of mi 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 ei 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 Ri yuan or Ei 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.

Input

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 ci, di, mi, pi (0 ≤ ci, di, mi, pi ≤ 104), 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 ei, Ri, Ei (0 ≤ ei ≤ 108, 0 ≤ Ri, Ei ≤ 104), 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 × 105.

Output

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.

Example
Input
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
Output
170
-1
Note

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.