/ Vijos / 题库 /

笨笨的西瓜种植

笨笨的西瓜种植

背景

笨笨:小西瓜,小西瓜~
路人甲:不会呀,这西瓜明明就大着啊……
笨笨:那……大西瓜,大西瓜~
路人甲:这么快就改口了……
笨笨:西瓜西瓜~可爱的西瓜~

描述

笨笨种了一块西瓜地,但这块西瓜地的种植范围是一条直线的……
笨笨在一番研究过后,得出了m个结论,这m个结论可以使他收获的西瓜最多。

笨笨的结论是这样的:
从西瓜地B处到E处至少要种植T个西瓜,这个范围的收获就可以最大化。

笨笨不想那么辛苦,所以他想种植的西瓜尽量少,而又满足每一个所得的结论。

格式

输入格式

第一行两个数n,m(0<n<=5000,0<=m<=3000),表示笨笨的西瓜地长n,笨笨得出m个结论。

接下来m行表示笨笨的m个结论,每行三个数b,e,t(1<=b<=e<=n,0<=t<=e-b+1)。

输出格式

输出笨笨最少需种植多少西瓜。

样例1

样例输入1

9 4
1 4 2
4 6 2
8 9 2
3 5 2

样例输出1

5

限制

1s

提示

基本上来说,笨笨的西瓜地就是一条壮观的线……

来源

笨笨原创。

信息

ID
1589
难度
6
分类
贪心 点击显示
标签
递交数
1981
已通过
529
通过率
27%
上传者

相关

在下列训练计划中:

RP++分类题库

NOIP代码+思维

在下列比赛中:

笨笨工作室2009提高组模拟赛