题目描述

一条直线上有 $n$ 个位置，编号从 $1$ 到 $n$。每个位置最多放置一个标记。

现有 $h$ 个需求，每个需求指定一个区间 $[b, e]$，要求在该区间内至少放置 $t$ 个标记。不同需求的区间可以重叠。

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

输入格式

第一行一个整数 $n$，表示位置总数。

第二行一个整数 $h$，表示需求数量。

接下来 $h$ 行，每行三个整数 $b, e, t$，表示在区间 $[b, e]$ 内至少需要 $t$ 个标记。

输出格式

输出一行一个整数，表示最少需要放置的标记数量。

样例

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

5

提示

对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^4$，$1 \le h \le 5 \times 10^3$，$1 \le b \le e \le n$，$1 \le t \le e - b + 1$。