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 non-optimal.

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:
18
Warning: large Input/Output data, be careful with certain languages

hide comments
aman_sachin200: 2018-06-13 21:51:12

Nice One!!!Dp+Binary Search :)....The problem statement is wrong...end time and starting time of different jobs cant be same....for Top-Down approach,precalculate next index to choose using Binary Search!!
@ayushi1807 nothing wrong but you have to keep track of previous element chosen which will result in an extra DP state and thus will increase space and time complexity and result in TLE....

Last edit: 2018-06-13 21:52:50
ayushi1807: 2018-05-17 14:07:21

Can any one tell what's wrong with this approach --> Sorting by start time and each time making two choices of either selecting(if its start time is greater than the end time of last chosen job) or not selecting the current job and then returning the max of both the answers ..

Last edit: 2018-05-17 14:08:48
ani_sharma1997: 2018-05-11 18:30:52

for people refering spoj toolkit it seems they have given wrong input-output . costed me 2 WA

imperfectboy: 2018-03-18 07:12:14

job scheduling .... with linear search and cin/cout - 0.18
with binary search and cin/cout - 0.07
with binary search and scanf/printf - 0.03

amitboss: 2018-01-30 16:36:36

aa

Last edit: 2018-01-30 16:38:24
cao_aba: 2018-01-16 14:16:19

It seem. there is a problem at test case folow:
4
0 9 18
3 7 14
5 9 7
6 9 8
4
0 9 18
3 5 14
5 9 7
6 9 8

mastik5h_1998: 2017-09-27 14:36:47

wrong problem statement.....realized after 1 wa.
dont consider same starting and ending time in sheduling of different flights

coolio_1: 2017-07-11 11:28:46

How to solve it in 0.00? The best I could get was 0.03 using CPP14! :-|

tech123: 2017-05-19 14:29:49

Easy dp problem :)

deepak_bulani1: 2017-05-14 21:28:01

weighted job scheduling!!


Added by:Adrian Kuegel
Date:2004-07-13
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Southwestern European Regional Contest, Paris 2003