Inventory

A factory produces products as follows. There are N days in the coming production season. Each morning the factory orders materials. At noon the materials will arrive and shipped into a warehouse. In the afternoon the factory produces products using the material in the warehouse. There is only one kind of material and one kind of product, and one unit of materials can make one unit of product. The factory needs to produce exactly di products on the i-th day of the production season, where i is between 1 and N. Also if the factory does not use all the materials in the warehouse, it can use them later, but the material can only be stored in the warehouse for up to 2 days, after that they cannot be used to make products. That is, if a material was shipped to the factory on the i-th day, it can be used only on the i-th and i + 1-th day. We want to order materials for this factory with minimum cost. Let pi be the price of material on the i-th day and ni be the maximum number of units of material one can order on the i-th day. Both pi and ni are changing daily. Note that we may want to order more materials when they are cheap, but keep in mind that we can order at most ni units on the i-th day, and we must use the materials within two days after we order them. Fortunately, the warehouse is large enough to store all materials for the entire production season, so we do not need to worry about its capacity. Instead we only need to determine the amount of materials to order for each day, so that we can produce di products on the i-th day, and the entire material cost is minimized. Technical Specification

1. The number of cases is a positive integer no more than 100.
2. The number of days N is a positive integer no more than 1000. 3. 1≤pi,di ≤100,1≤ni ≤10000foreveryi. Input The first line of the input file contains an integer indicating the number of test cases to follow. The first line of the test case has the number of days (N) in the production season. Each of the next N lines has the price of material per unit (pi), the maximum number of units of material (ni) the factory can order, and the amount of materials (di) ordered for that day. Output For each test case, output the minimum material cost to produce all products. It is assumed that there exists a solution. Sample Input 2 3 59 5 1 96 9 1 67 6 11 3 26 3 1

2/2 76 9 11 56 6 2 Sample Output 1000 874