RENT  Rent your airplane and make money
"ABEAS Corp." is a very small company that owns a single airplane. The customers of ABEAS Corp are large airline companies which rent the airplane to accommodate occasional overcapacity.
Customers send renting orders that consist of a time interval and a price that the customer is ready to pay for renting the airplane during the given time period. Orders of all the customers are known in advance. Of course, not all orders can be accommodated and some orders have to be declined. Eugene LAWLER, the Chief Scientific Officer of ABEAS Corp would like to maximize the profit of the company.
You are requested to compute an optimal solution.
Small Example
Consider for instance the case where the company has 4 orders:
 Order 1 (start time 0, duration 5, price 10)
 Order 2 (start time 3, duration 7, price 8)
 Order 3 (start time 5, duration 9, price 7)
 Order 4 (start time 6, duration 9, price 8)
The optimal solution consists in declining Order 2 and 3 and the gain
is 10+8 = 18.
Note that the solution made of Order 1 and 3 is feasible (the airplane
is rented with no interruption from time 0 to time 14) but nonoptimal.
Input
The first line of the input contains a number T ≤ 30 that indicates the number of test cases to follow. The first line of each test case contains the number of orders n (n ≤ 10000). In the following n lines the orders are given. Each order is described by 3 integer values: The start time of the order st (0 ≤ st < 1000000), the duration d of the order (0 < d < 1000000), and the price p (0 < p < 100000) the customer is ready to pay for this order.
Output
You are required to compute an optimal solution. For each test case your program has to write the total price paid by the airlines.
Example
Input: 1 4 0 5 10 3 7 14 5 9 7 6 9 8 Output: 18Warning: large Input/Output data, be careful with certain languages
hide comments
Adrian Kuegel:
20121011 15:08:38
No, they can be in any order. But sorting them yourself should be easy, right? 

Soumajyoti:
20120928 19:08:25
Are the inputs given in sorted order of their start times??


Adrian Kuegel:
20110802 10:40:39
No, there are no blank lines between different test cases (if there would be blank lines, this would be written in the problem description).


Balasubramanian:
20110730 17:24:26
Well, can someone tell me if there will be a blank line between every set of test cases? 

.::Manish Kumar::.:
20110630 07:13:29
similar to ACTIV 

Adrian Kuegel:
20110624 07:24:10
@Eclipse: I am not an admin, but as the one who added the problem I can see your submission. The only thing I will tell you is that your submission fails on many test cases. You may try to develop a brute force solution and check it locally against your solution which got WA. Last edit: 20110624 07:24:37 

hemezh:
20110622 12:30:11
@ADMIN: Can u please give me a test case in which my submission is wrong? Please check 5277912. 

Adrian Kuegel:
20110622 07:50:53
See my comment on 20100224 16:00:08 

Archit Goel:
20110618 21:19:23
i have the same question as seshadri.


Adrian Kuegel:
20100416 08:35:49
That looks quite funny. Of course you posted it earlier than me :) 
Added by:  Adrian Kuegel 
Date:  20040713 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Southwestern European Regional Contest, Paris 2003 