A5896. 「USACO 2019.12 Platinum」Greedy Pie Eaters
编程题
提高+/省选-
知识点
题目描述
**题目译自 [USACO 2019 December Contest, Platinum](http://usaco.org/index.php?page=dec19results) Problem 1. [Greedy Pie Eaters](http://usaco.org/index.php?page=viewproblem2&cpid=972)**
Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1\ldots M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1\ldots N$。第 $i$ 头奶牛喜欢吃编号在 $[l_i,r_i]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $[1, 10^6]$ 中的正整数。
Farmer John 可以选择一个奶牛序列 $c_1,c_2,\ldots c_K$，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 $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}$）是多少。
Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1\ldots M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1\ldots N$。第 $i$ 头奶牛喜欢吃编号在 $[l_i,r_i]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $[1, 10^6]$ 中的正整数。
Farmer John 可以选择一个奶牛序列 $c_1,c_2,\ldots c_K$，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 $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$；
接下来 $M$ 行，每行三个正整数 $w_i,l_i,r_i$。
接下来 $M$ 行，每行三个正整数 $w_i,l_i,r_i$。
输出格式
输出对于一个合法的序列，最大可能的体重值。
输入输出样例
输入 #1
2 2 100 1 2 100 1 1
输出 #1
200
说明/提示
对于全部数据，$1\le N\le 300,1\le M\le \frac{N(N-1)}{2},1\le l_i\le r_i\le N,1\le w_i\le 10^6$。
对于测试点 $2\sim 5$，满足 $N\le 50,M\le 20$；
对于测试点 $6\sim 9$，满足 $N\le 50$。
对于测试点 $2\sim 5$，满足 $N\le 50,M\le 20$；
对于测试点 $6\sim 9$，满足 $N\le 50$。