Chef and the Orders

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef gets N orders. The orders are numbered from 1 to N. He gets order i at S_{i} time, and this order contains X_{i} number of items. Chef needs to serve each of these X_{i} items before D_{i} time and for each unit of items he cannot cook before this deadline he needs to pay P_{i} unit of money as penalty. Given all of the orders, help the Chef to minimize the penalty he will have to pay.
Important Note: Chef can cook at most one item at a unit time and for each item he needs exactly one unit of time to cook. Also Chef can serve an item instantly, when the item is cooked. If Chef wants to serve an item at time t, then the latest he can cook that item is at time time t. In another words, for order i Chef can cook the items at time units S_{i}, S_{i}+1, S_{i}+2, ..., D_{i}1. Please note, that Chef can not cook items from order i exactly at time unit D_{i}.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case starts with a line containing N the number of orders. Each of the next N lines contains the description of an order. Order i is given as a four integers S_{i}, X_{i}, D_{i} and P_{i} in a single line separated by a single space.
Output
For each test case, output a single line containing the minimum amount of penalty Chef has to pay.
Constraints
 1 ≤ T ≤ 50
 1 ≤ N ≤ 200
 1 ≤ S_{i} ≤ 10^{8}
 1 ≤ X_{i} ≤ 10^{8}
 1 ≤ D_{i} ≤ 10^{8}
 1 ≤ P_{i} ≤ 10^{8}
 S_{i}+X_{i} ≤ D_{i}
Example
Input: 5 1 1 5 6 10 2 1 5 6 10 1 5 6 10 2 1 5 6 1 1 5 6 10 2 1 5 6 10 6 5 11 10 4 5 8 15 20 11 8 20 21 16 8 25 22 21 8 30 23 Output: 0 50 5 0 147
Explanation
Example 1: There is only 1 order and all of the items from this order can be served. So zero penalty
Example 2: There are two orders and you cannot serve 5 items. You can select these 5 items from any order.
Example 3: There are two orders and you cannot serve 5 items. But it is better not to serve these 5 items from the first order.
Author:  satej 
Tester:  gerald 
Editorial  http://discuss.codechef.com/problems/ORDERAAM 
Tags  cook42, greedy, hard, mincostflow, satej 
Date Added:  6012014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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
HELP
If you are still having problems, see a sample solution here. 