No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

题目描述

路边的地区被分割成块，并被编号成 $1, 2, \ldots,n$。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码 $b$，$e$，$t$。这三个数表示该居民想在地区 $b$ 和 $e$ 之间（包括 $b$ 和 $e$）种至少 $t$ 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入格式

输入的第一行是一个整数，代表区域的个数 $n$。

输入的第二行是一个整数，代表房子个数 $h$。

第 $3$ 到第 $(h + 2)$ 行，每行三个整数，第 $(i + 2)$ 行的整数依次为 $b_i, e_i, t_i$，代表第 $i$ 个居民想在 $b_i$ 和 $e_i$ 之间种至少 $t_i$ 棵树。

输出格式

输出一行一个整数，代表最少的树木个数。

样例 #1

样例输入 #1

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

样例输出 #1

5

提示

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \leq n \leq 3 \times 10^4$，$1 \leq h \leq 5 \times 10^3$。
• $1 \leq b_i \leq e_i \leq n$，$1 \leq t_i \leq e_i - b_i + 1$。