3359. [USACO19 Dec Platinum]Greedy Pie Eaters

【题目描述】

本题面由 @数声风笛 翻译。

Farmer John 有 $M$ 头牛，方便地标为 $ 1 … M$ ，他们偶尔会因吃草而步伐变化。作为对牛的一种招待，Farmer John 烤了 $N$ 个馅饼 $( 1 ≤ N ≤ 300 )$ ，标记为 $1 … N$。母牛 $i$ 的馅饼的标签范围为 $[ l_i , r_i ]$，并且没有两只牛的馅饼范围完全相同。 牛 $i$ 还具有权重 $w_i$，它是$1 … 10^6$ 范围内的整数。 

Farmer John 可以选择一头母牛$ c_1 , c_2 ,…,c_K$ 的顺序，此后选定的母牛将按该顺序轮流进食。不幸的是，母牛不知道如何分享！轮到$c_i$.牛$c_i$吃东西时，她会消耗掉她喜欢的所有馅饼——即 $[ l_{c_i} , r_{c_i}]$ 内的所有剩余馅饼。Farmer John 想避免这种情况，因为轮到母牛吃东西了，但是她喜欢的所有馅饼都已经被消耗掉了。因此，他希望您计算序列 $c_1,c_2,\ldots, c_K$ 的最大可能总重量$(w_{c_1}+w_{c_2}+\ldots+w_{c_K})$，序列中的每头牛至少要吃一个馅饼。

【输入格式】

第一行包含两个整数 $N$ 和 $M$ $\left(1\le M\le \frac{N(N+1)}{2}\right)$。
接下来的 $M$ 行分别以整数 $w_i , l_i$ 和 $r_i$ 描述第 $i$ 头牛。

【输出格式】

输出有效序列的最大可能总权重。

【样例输入】

2 2
100 1 2
100 1 1

【样例输出】

200

【样例解释】

在此示例中，如果母牛 1 首先进食，那么母牛 2 将没有食物可吃。

但是，如果母牛 2 首先吃东西，那么母牛 1 将只吃第二个馅饼，就可以满足。

【提示】

对于$ 29\% $的测试数据(测试点$ 1\sim5 $)，满足$ N ≤ 50 , M ≤ 20 $。

另有$ 24\% $的测试数据(测试点$ 6\sim9 $)，满足$ N ≤ 50 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月公开赛 Platinum 组