After having tried a number of different games with your friends, you decide that Poker is a perfect combination of your favourite pastimes: games and statistics! Being computer science students, you naturally start gravitating towards devising optimal playing strategies, and it doesn't take long until you desire to show the world your newly found faculties by playing professionals and taking their money.

Your plan is to win as much money as you can by playing as many Poker tournaments in a single month as time allows. Looking at a tournament schedule, however, you notice that you cannot play all tournaments since some of them overlap. Before you can meet your opponents in battle, you thus need to find the optimal selection of tournaments that, if won, maximize your prize money.


The input contains several test cases, the number of which is specified by a number \(1 \leq t \leq 20\) on the first line.

Each test case starts with a line that contains the number of tournaments \(1 \leq n \leq 5000\). What follows are \(n\) lines with three numbers \(a\), \(b\), \(p\) separated by spaces (\(1 \leq a \leq b \leq 5000\) and \(1 \leq p \leq 10000\)) that specify a tournament's first day, last day, and prize money, respectively.

Two tournaments are considered to be overlapping even if the first one ends on the same day the second one starts. Two test cases may or may not be separated by a blank line.


For each test case, print a line that contains the maximum amount of money you could win.

Sample Input

1 5 1000
10 15 1000
2 12 3000
1 1 500
2 5 500
3 7 1000
6 7 600

Sample Output


This problem is based on a problem first published at the Technische Universität München and is licensed under a Creative Commons Attribution Share-Alike license (cc by-sa).

Upload Solution

Please log in to submit your solution.


Difficulty (0 votes)
Average test runtime 0.47
Points (changes over time) 10
Tried by 5 users
Solved by 5 users

Global ranking

# Name Runtime Points worth
1 ,s/java/NaN/gi 0.16 23
2 Connor 0.47 8
3 Dark 0.49 7
4 Mac 0.49 7
5 Skøgland 0.76 5