题目描述

一条街道的一边有几座房子。因为环保原因居民想要在路边种些树，路边的地区被分割成 $n$ 块，并被编号为 $1...n$ ，每一块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个数 $b，e，t$ 这三个数分别表示该居民想在 $b$ 和 $e$ 之间最少种 $t$ 棵树，当然， $b ≤ e$ ， $t ≤ e - b + 1$ ，允许居民想种树的子区域可以交叉。

出于资金紧缺的原因，环保部门请你求出能够满足所有居民的树所需种的树的最少数量。

输入

第一行为 $n$ ，表示区域的个数；

第二行为 $h$ ，表示房子的数目；

下面 $h$ 行描述居民的需要： $b、e、t$ ($0 < b ≤ e ≤ 30000$ ， $t ≤ e - b + 1$) 分别用一个空格分开。

输出

输出一个数，为满足所有居民的要求，所需要种树的最少数量。

样例

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

5

说明

$30\%$ 的数据满足 $0 < n ≤ 1000$ ， $0 < h ≤ 500$ 。

$100\%$ 的数据满足 $0 < n ≤ 30000$ ， $0 < h ≤ 5000$ 。