[USACO19DEC] Greedy Pie Eaters P

题目背景

Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked $N$ pies ($1 \leq N \leq 300$), labeled $1 \ldots N$. Cow $i$ enjoys pies with labels in the range $[l_i, r_i]$ (from $l_i$ to $r_i$ inclusive), and no two cows enjoy the exact same range of pies. Cow $i$ also has a weight, $w_i$, which is an integer in the range $1 \ldots 10^6$. Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which the selected cows will take turns eating in that order. Unfortunately, the cows don't know how to share! When it is cow $c_i$'s turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval $[l_{c_i},r_{c_i}]$. Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight ($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$) of a sequence $c_1,c_2,\ldots, c_K$ for which each cow in the sequence eats at least one pie.

题目描述

Farmer John 有 $M$ 头奶牛,为了方便,编号为 $1,\dots,M$。这些奶牛平时都吃青草,但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃,这 $N$ 个派编号为 $1,\dots,N$。第 $i$ 头奶牛喜欢吃编号在 $\left[ l_i,r_i \right]$ 中的派(包括两端),并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$,这是一个在 $\left[ 1,10^6 \right]$ 中的正整数。 Farmer John 可以选择一个奶牛序列 $c_1,c_2,\dots,c_K$,并让这些奶牛按这个顺序轮流吃派。不幸的是,这些奶牛不知道分享!当奶牛 吃派时,她会把她喜欢吃的派都吃掉——也就是说,她会吃掉编号在 $[l_{c_i},r_{c_i}]$ 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时,她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此,他想让你计算,要使奶牛按 $c_1,c_2,\dots,c_K$ 的顺序吃派,轮到这头奶牛时她喜欢的派至少剩余一个的情况下,这些奶牛的最大可能体重($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$)是多少。

输入输出格式

输入格式


第一行包含两个正整数 $N,M$; 接下来 $M$ 行,每行三个正整数 $w_i,l_i,r_i$。

输出格式


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

输入输出样例

输入样例 #1

2 2
100 1 2
100 1 1

输出样例 #1

200

说明

#### 样例解释 在这个样例中,如果奶牛 $1$ 先吃,那么奶牛 $2$ 就吃不到派了。然而,先让奶牛 $2$ 吃,然后奶牛 $1$ 只吃编号为 $2$ 的派,仍可以满足条件。 对于全部数据,$1 \le N \le 300,1 \le M \le \dfrac{N(N-1)}{2},1 \le l_i,r_i \le N,1 \le w_i \le 10^6$。 #### 数据范围 对于测试点 $2-5$,满足 $N \le 50,M \le 20$; 对于测试点 $6-9$,满足 $N \le 50$。 USACO 2019 December 铂金组T1