#3226. 「USACO 2019.12 Platinum」Greedy Pie Eaters

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

题目译自 USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters

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

输出格式

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

样例

样例输入

2 2
100 1 2
100 1 1

样例输出

200

样例说明

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

数据范围与提示

对于全部数据, 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