该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $\red {n}$ 个区间 $\red {[a_i ,b _i ]}$和 $\red {n}$ 个整数 $\red {c _i}$ 。

你需要构造一个整数集合 $\red {Z}$，使得$\red {∀i∈[1,n]}$,$\red Z$中满足$\red {a _i≤x≤b_i}$的整数 $\red {x}$ 不少于 $\red {c_i}$ 个。

求这样的整数集合 $\red {Z}$ 最少包含多少个数。

输入格式

第一行包含$\red{2}$个整数$\red{m}$ （$\red{b_i}$ 不超过$\red{m}$）和 $\red {n}$。

接下来$\red {n}$行，每行包含三个整数$\red {a _i ,b _i ,c_i}$ 。

输出格式

输出一个整数表示结果。

样例

输入样例

11 5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例

6

提示

$\red {1≤n≤50000}$,

$\red {0≤a _i ,b _i ≤50000}$,

$\red {1≤c _i ≤b_i −a _i +1}$