解题思路

题目中有 $n$ 个方格堆，初始高度均为 $0$。共有 $m$ 次操作，每次操作会对区间 $[l_i,r_i]$ 的所有方格堆高度增加 $d_i$。

设最终第 $j$ 个方格堆的高度为：

题目内容

方格世界中所有方格的长宽高均为$1$米。方格世界中有$n$个方格堆，编号依次为$1,2...n$。每个方格堆中的方格都是按照从下到上的方式堆成一列(假设有$k$个方格，则这$k$个方格堆成了一个长宽均为$1$米，高为$k$米的长方体)。初始时每个方格堆中的方格数量均为$0$。方格世界会下$m$场“方格雨”，第$i$场“方格雨”会使得编号在$l_i$到$r_i$之间的方格堆的方格数量增加$d_i$。

定义$f(x)$表示经过“方格雨”后方格世界中高度大于等于$x$米的方格堆个数。你需要计算$f(1),f(2)..f(10^{100})$中一共有多少不同的取值。

输入描述

输入第一行有两个整数$n(1≤n≤10^9)$和$m(1≤m≤10^5)$，分别表示方格世界中方格堆的个数、“方格雨”的次数。

接下来m行中，第$i$行有三个整数$l_i,r_i(1≤l_i≤r_i≤n)$和$d_i(1≤d_i≤10)$,分别表示“方格雨”作用的方格堆范围和增加的方格数量。

输出描述

输出一个整数，表示$f(1),f(2)...(10^{100})$中一共有多少不同的取值。

样例1

输入

10 4
7 8 5
5 7 5
1 2 1
3 5 3

输出

6 

说明

第一场“方格雨”后各个方格堆中方格数量:$[0\ 0\ 0\ 0\ 0\ 0\ 5\ 5\ 0\ 0]$;

第二场“方格雨”后各个方格堆中方格数量:$[0\ 0\ 0\ 0\ 5\ 5\ 10\ 5\ 0\ 0]$;

第三场“方格雨“后各个方格堆中方格数量:$[1\ 1\ 0\ 0\ 5\ 5\ 10\ 5\ 0\ 0]$;

第四场“方格雨”后各个方格堆中方格数量:$[1\ 1\ 3\ 3\ 8\ 5\ 10\ 5\ 0\ 0]$。

依次计算$f(1)=8，f(2)=6,f(3)=6,f(4)=4,f(5)=4，f(6)=2,f(7)=2, f(8)=2, f(9)=1, f(10)=1, f(11)=f(12)=...=f (10^{100})=0$。{$8\ 6\ 6\ 4\ 4\ 2\ 2\ 2\ 1\ 1\ 0...0$}中一共有$6$个不同的取值。