2615. 会议安排

单点时限: 2.0 sec

内存限制: 256 MB

科研人员与相关领域的国内外同行进行适时的接触与充分的交流,对于促进提高他们的科研业务水平,并及时掌握科研动态是十分必要而且重要的。ECNU 为了走在科技的前沿,于是决定派遣一些学者出去参加会议。由于这些会议具有不同的级别,因此对于科研人员可能带来的科研上的促进作用也就可能不同。但是一个学者不能同时参加两个会议。而且,如果一个学者需要连续参加两个会议,第二个会议的开始时间要晚于第一个会议的结束时间 ..

现在给出一些会议的起始时间和终止时间,并给出这些会议对应的促进值,请你计算出一个学者能够得到的最大的促进值。

输入格式

第一行为一个整数 T, 表示测数数据的组数。
每组数据第一行为整数 n(1<=n<=300),代表有 n 个会议,然后有 n 行数据,每行给出 3 个整数 s(会议开始时间),t(会议终止时间),w(会议相对应的促进作用).(0<=s<=t<=365,0<w<100)

输出格式

输出能够得到的最大的促进作用。

每组测试数据输出占一行。

样例

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

67 人解决,94 人已尝试。

93 份提交通过,共有 285 份提交。

4.0 EMB 奖励。

创建: 13 年前.

修改: 4 年,8 月前.

最后提交: 1 月,3 周前.

来源: 华东师范大学2009校赛

题目标签