Avoid Wasting

All submissions for this problem are available.
Today Tomya buys N retort pouches of food in Chef Ciel's restaurant. The ith retort pouch contains V_{i} units of food, and its useby date is the U_{i}th day (1origin). Moreover, food from the ith retort pouch can be eaten only within L_{i} days after it was opened. Namely, if Tomya will open the ith retort pouch on the x_{i}th day, she can eat food units from it on the kth day if and only if x_{i} ≤ k ≤ min(U_{i}, x_{i}+L_{i}−1).
The retort pouches in Ciel's restaurant are designed in such a way that if V_{i} < V_{j}, then U_{i} ≤ U_{j}.
Tomya will eat at most two units of food everyday. However after the min(U_{i}, x_{i}+L_{i}−1)th day, uneaten food units in the ith retort pouch must be discarded. Your task is to decide when to open each of the retort pouches and which food unit(s) to eat each day in such a way that the number of discarded units will be minimum.
There is also a restriction that once you open some pouch, food units from previously opened pouches should be discarded.
The above restriction is an addition to the problem statement that was made after the contest. We are extremely sorry about that. We all had missed the possibility to achieve better score without this restriction in some situations. We are grateful to Mikhail Kever for pointing out our mistake.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the number of retort pouches.
Each of the following N lines contains 3 space separated integers V_{i}, U_{i}, L_{i} denoting the parameters of the ith pouch.
Output
For each test case, output a single line containing the minimum number of food units which Tomya must discard.
Constraints
 1 ≤ T ≤ 2013
 1 ≤ N ≤ 2013
 1 ≤ V_{i}, U_{i}, L_{i} ≤ 20000000000000 (2 * 10^{13})
 If V_{i} < V_{j}, then U_{i} ≤ U_{j}
 The sum of N in one test file does not exceed 20130.
Example
Input: 3 3 8 9 5 7 5 3 10 100 1 3 5 4 3 7 8 5 8 10 4 1 10000 1 10000 Output: 9 0 9998
Explanation
Example case 1. One of the optimal ways is the following:
The 1st pouch is opened on the day x_{1} = 4,
the 2nd pouch is opened on the day x_{2} = 1,
the 3rd pouch is opened on the day x_{3} = 8,
then
the 1st pouch is available at the interval [4, 8],
the 2nd pouch is available at the interval [1, 3],
the 3rd pouch is available at the interval [8, 8].
On days 1, 2, 3, Tomya eats 2 units of the 2nd pouch each day.
On days 4, 5, 6, 7 Tomya eats 2 units of the 1st pouch each day.
On day 8, Tomya eats 2 units of the 3rd pouch.
In this case, Tomya discard the 1 unit of the 1st pouch, and 8 units of the 3rd pouch.
Example case 2. There is only one optimal way as follows:
The 1st pouch is opened on the day x_{1} = 1,
the 2nd pouch is opened on the day x_{2} = 3,
the 3rd pouch is opened on the day x_{3} = 7,
then
the 1st pouch is available at the interval [1, 3],
the 2nd pouch is available at the interval [3, 7],
the 3rd pouch is available at the interval [7, 10].
On days 1, 2, Tomya eats 2 units of the 1st pouch each day.
On day 3, Tomya eats 1 unit of the 1st pouch and 1 unit of the 2nd pouch.
On days 4, 5, 6, Tomya eats 2 units of the 2nd pouch each day.
On days 7, 8, 9, 10, Tomya eats 2 units of the 3rd pouch each day.
In this case, Tomya can eat all units of food.
Example case 3. Please note that here L_{1} is larger than U_{1}.
Author:  laycurse 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/AVDWAST 
Tags  cook30, greedy, laycurse, mediumhard 
Date Added:  2012013 
Time Limit:  2.013 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions