#5300. Cover

内存限制:256 MiB 时间限制:1500 ms 输入文件:cover.in 输出文件:cover.out
题目类型:传统 评测方式:文本比较
上传者: zhouhao

题目描述

小A现在想用m条彩灯去装饰家中的走廊,走廊可以视作一个[1,n]的区间,每一条彩灯都能覆盖一 个子区间,并且有一个特定的美观程度。 然而为了降低装饰的难度,彩灯能够覆盖的区间两两之间只有包含和不相交的关系,同时为了避免光污 染,他希望每个[1,n]中的点至多被k条彩灯覆盖。 现在小A希望你能告诉他,k= 1,2,..., m时,选出的彩灯的最大美观程度之和时多少。

输入格式

第一行两个整数n,m表示区间的长度与彩灯的数量。 接下来m行,每行三个整数li,ri,ai表示一条彩灯能够覆盖的区间以及它的美观程度。

输出格式

输出一行 𝑛 个整数,第 𝑖 个数表示 𝑙 = 𝑖 时的最大美观程度。

样例

Sample Input

25 6
1 2 10
2 3 10
1 3 21
3 4 10
4 5 10
3 5 19

Sample Output

41 80 80 80 80 80

数据范围与提示

对于 25% 的数据,m ≤ 5000 对于 45% 的数据,n,m ≤ 5000 对于另外 25% 的数据,所有ai相同 对于 100% 的数据,1 ≤ l 𝑖 ≤ 𝑟 𝑖 ≤ n,m ≤ 300000,𝑎 𝑖 ≤ 1000000000