Event Organizer

All submissions for this problem are available.
Chef Po has given an online advertisement to provide Event organizing services. Chef got a huge response for his advertisement. He got various orders to conduct the events from different organizations. In turn, Chef will receive a compensation depend upon the type of event and the total numbers of persons in the event. Chef has received N orders for conducting events in this weekend in all. As weekend consists of two days all events will take place during the period of 48 hours. For the ith order the corresponding event will start at S_{i} hours, ends at E_{i} hours and Chef will receive a compensation C_{i} for this event. For example, if S_{i} = 17 and E_{i} = 22 then duration of event is 22 – 17 = 5 hours and its time period is 17:00 – 22:00 of Saturday. Hours of Sunday are numbered by numbers from 24 to 48. So, for example, 10:00 of Sunday will be represented as 10 + 24 = 34. Because Chef is a newbie, the organizations had put a condition that Chef will receive a compensation for the event if and only if he is available for the entire duration of the event. It means that he can not choose overlapping events. Note, however, that if some event starts just in the moment another event has finished the Chef can safely conduct them both.
In general Chef will obey the orders on first come first serve basis. But on weekends Chef will select the orders in such a way that the total compensation for all the events he will conduct will be the maximal. Now your task is to help Chef and find this maximal total compensation.
Input
The first line of the input contains an integer T, the number of test cases. T test cases follow. The first line of each test case contains an integer N, the number of received orders for conducting events. Each of the next N lines contains three space separated integers S_{i}, E_{i}, C_{i}, the parameters of the ith event described in the problem statement.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 2000
0 ≤ S_{i} < E_{i} ≤ 48
0 ≤ C_{i} ≤ 10^{6}
Output
Output for each test case should contain a single integer in a separate line, the maximal compensation Chef Po can get.
Example
Input: 2 4 1 2 100 2 3 200 3 4 1600 1 3 2100 3 1 10 2000 2 5 100 6 9 400 Output: 3700 2000
Explanation
Case 1. The best choice here is to conduct 3rd and 4th events. The total compensation is equal to 1600 + 2100 = 3700. These events do not overlap since 3rd event starts just after the finish of the 4th one. Alternatively we can conduct first three events that also do not overlap. But in this case compensation will be only 100 + 200 + 1600 = 1900.
Case 2. Note that first event overlaps with both second and third events, while the last two events do not overlap. Hence there are two reasonable choices available for Chef. One is to take just the first order with total compensation 2000 and the second one is to take the last two orders with total compensation 100 + 400 = 500. Clearly the first choice is better. Hence the answer is 2000.
Author:  khadarbasha 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/MAXCOMP 
Tags  khadarbasha oct12 simple 
Date Added:  31052012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions