Greedy Pie Eaters

题目描述:

Farmer John 有 M 头奶牛，为了方便，编号为 1,…,M。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 N 个派请奶牛吃，这 N 个派编号为 1,…,N。第 i 头奶牛喜欢吃编号在 [li​,ri​] 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 i 头奶牛有一个体重 wi​，这是一个在 [1,10⁶] 中的正整数。

Farmer John 可以选择一个奶牛序列c1​,c2​,…,cK​，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 [lci​​,rci​​] 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 c1​,c2​,…,cK​ 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（wc1​​+wc2​​+…+wcK​​）是多少。

输入格式:

第一行包含两个正整数 N,M；

接下来 M 行，每行三个正整数wi​,li​,ri​。

输出格式:

输出对于一个合法的序列，最大可能的体重值。

样例输入:

2 2
100 1 2
100 1 1

样例输出:

200

提示:

样例解释

在这个样例中，如果奶牛 1 先吃，那么奶牛 2 就吃不到派了。然而，先让奶牛2 吃，然后奶牛 1 只吃编号为 2 的派，仍可以满足条件。

对于全部数据，1≤N≤300,1≤M≤2N(N−1)​,1≤li​,ri​≤N,1≤wi​≤10⁶。

数据范围

对于测试点 2−5，满足 N≤50,M≤20；

对于测试点 6−9，满足N≤50。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2019 DEC Platinum