提示: 欢迎访问OurACM平台。
Problem 2211 提莫的蘑菇田

Accept: 8    Submit: 64
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

小菇凉和小光头在提莫的蘑菇田里采走的蘑菇扇子妈妈很喜欢,所以小菇凉特地回来感谢提莫,并且教会它一种奇怪的黑暗魔法,可以使得某种蘑菇在固定的 Si 时刻种下后快速在 Ti 时刻成熟。双十一到了,提莫觉得很缺钱,所以他决定利用这个黑魔法尽可能多地种植出蘑菇换到更多的金币。

提莫有N块蘑菇田,他有M种蘑菇可以种植,同时刻中每块蘑菇田只能种植一种蘑菇,对于每种蘑菇只能种植一次,且第 i 种蘑菇只有在固定的 Si 到Ti 时间内种植才能使用黑魔法快速生长,并能用这个蘑菇田的收获换得 Vi 的金币。

提莫想知道他最多能获得多少金币。

特别的:对于某两种蘑菇 i 和蘑菇 j ,如果Sj==Ti,那么蘑菇 j 不能立即种植在蘑菇 i 所在田地上。

Input

输入共T(<=100)组数据。

输入第一行包括两个整数,N(<=50),M(<=100)。 N为提莫总共有的蘑菇田的数目,M表示提莫可以种植的蘑菇种数。

接下来M行,每行三个整数 Si , Ti 和 Vi (<2^31)表示第i种蘑菇能在 Si 到Ti 的时间内种植一次,收获换得Vi的钱币。

Output

输出一个整数( <2^31)表示提莫最多可获得的钱币。

Sample Input

1 2 4 1 2 4 2 5 8 1 7 9 1 2 6

Sample Output

17

Source

FOJ有奖月赛-2015年11月

Submit  Back  Status  Discuss