文理学院程序设计在线练习


又见最少失约

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 110   Accepted Submission(s): 47
Problem Description

我们明年将有许多重要的活动需要参加,可是由于活动太多,无法全部参加,请你帮我们安排,以便更有效地参加活动,使得参加活动的价值总和最大。

现在给出明年的全部活动的开始日期和结束日期,并给出这些活动对应的价值,请你计算能够得到的最大价值。

注意,由于活动是以天为基本单位,因此,能够参加的相邻两个活动必须满足:第二个活动的开始日期要晚于第一个活动的结束日期。

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。
每组数据第一行为整数n(1<=n<=300),代表有n个活动。
以下的n行每行包括三个由空格隔开的整数i,j,k,其中1<=i<=j<=365,0<k<100.分别代表活动的开始日期、结束日期和价值。

Output

对于每组测试数据,输出能够得到的最大价值总和,每组测试数据输出占一行。

Sample Input
2
3
2 5 5
4 6 4
6 7 10
3
1 2 3
2 4 10
3 10 2
Sample Output
15
10
Author

flx

Source

usx第四届程序设计竞赛