题目描述

训练路线依次设置了编号为 $1,2,\ldots,m$ 的 $m$ 个候选标记点。你可以选择其中一些位置放置标记，每个位置最多放置一个标记。

现在有 $n$ 条训练要求。第 $i$ 条要求规定：闭区间 $[l_i,r_i]$ 内至少要有 $c_i$ 个已放置的标记。

请计算满足所有要求时，至少需要放置多少个标记。

输入格式

第一行输入两个整数 $m,n$。

接下来 $n$ 行，每行输入三个整数 $l_i,r_i,c_i$。

输出格式

输出一个整数，表示最少标记数。

样例

8 3
1 4 2
3 6 2
6 8 2

4

数据规模与约定

• $1\le m,n\le 5000$；
• $1\le l_i\le r_i\le m$；
• $1\le c_i\le r_i-l_i+1$。

题目保证存在满足全部要求的方案。