1014: 魔法阵(上古时期)
Description
为了夺取战争的胜利，大法师安东尼设置了一种特殊的魔法阵来为他的法师部队提供充足的能量。魔法阵中有N个水晶插槽，用1~N来标记，从左到右排成一排。魔法阵要发挥功效，必须在插槽中放置一些能量水晶。
根据上古时期的文字记载，魔法阵启动需要同时满足M个条件，我们用一个三元组（aibici）来描述第i个条件，表示第i个插槽到第j个插槽之间（包括第i个插槽和第j个插槽）必须至少有ci个插槽中放置了能量水晶，才能满足条件i。
在所有的插槽中都放置能量水晶显然可以启动这个魔法阵。但是由于能量水晶是一种非常昂贵而且稀缺的道具，制作起来非常耗时，而战争已经迫在眉睫。因此大法师想要知道：他至少需要制作多少能量水晶才能够启动这个魔法阵？
Input
输入文件名为 magic.in。
输入第一行为一个正整数N，代表有N个水晶插槽
输入第二行为一个正整数M，代表魔法阵启动需要同时满足M个条件
接下来M行，每行有三个整数ai、bi、ci，描述条件i
Output
输出文件名为 magic.out。
输出仅有一行，表示需要的最少水晶数量
Sample Input Copy
10
2
1 4 1
4 8 1
Sample Output Copy
1HINT
【输入输出样例2】
|
magic.in |
magic.out |
|
10 3 1 2 2 3 4 2 10 10 1
|
5 |
【样例解释】
对于第一个样例：魔法阵总共有10个插槽，启动魔法阵至少需要满足2个条件。
只要在4号插槽放置一个能量水晶，就可以同时满足条件1和条件2，所以答案为1。
【数据范围】
|
数据编号 |
N |
M |
|
1 |
1≤ N ≤ 10 |
= 1 |
|
2 |
= 2 |
|
|
3 |
= 3 |
|
|
4 |
1≤ N ≤ 20 |
5≤ M ≤ 20 |
|
5 |
||
|
6 |
||
|
7 |
1≤ N ≤ 100 |
20≤ M ≤ 100 |
|
8 |
||
|
9 |
1≤ N ≤ 5000 |
1≤ M ≤ 5000 |
|
10 |
注：对于100%的数据，都满足1 ≤ ai ≤ bi ≤ N 且 bi-ai+1 ≤ ci