广告问题2

成绩 100 开启时间 2020年02月20日 星期四 19:55
折扣 0.8 折扣时间 2020年02月20日 星期四 19:55
允许迟交 是 关闭时间 2020年02月20日 星期四 19:55
输入文件 ad2.in 输出文件 ad2.out

【题目描述】广告问题2（ad2）

一条街道分割成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