206013 - 广告问题2

一条街道分割成n块,编号为1…n,每块有一个广告栏,仅能贴一张广告。有w个命令,每个命令指定了三个数b,e,t,表示在b和e之间最少贴t个广告,问最少贴多少广告?

输入

第一行为n,表示分割块数。 第二行为w(w≤5 000),表示命令数。 随后为w行命令,每行命令包含三个数b,e,t(0<b≤e≤30 000,b≤e,t≤e-b+1)。

输出

输出一个数,表示最少贴的广告数。

样例

输入

8
4
2 4 1
4 6 2
7 8 2
3 7 2

输出

4
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题