每年圣诞节，Byteasar 都会用一串彩灯装饰他的家。然而今年，他打算第一次亲自挑选彩灯的颜色。他严谨（且有些古怪）的审美观告诉他，如果一串彩灯的某些片段具有相同的排列方式，那么这串彩灯就是漂亮的。此外，Byteasar 的妻子要求今年的彩灯要“多样化”，他将其理解为尽可能多地使用不同颜色。请帮助 Byteasar 确定他需要多少种颜色的灯。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($n \ge 2, m \ge 1$)，由单个空格分隔；它们分别指定了链中灯的数量和 Byteasar 的审美规则数量。我们将链中的灯从 $1$ 到 $n$ 进行编号。接下来的 $m$ 行，每行通过三个整数 $a_i, b_i$ 和 $l_i$ ($1 \le a_i, b_i, l_i$; $a_i \neq b_i$; $a_i, b_i \le n - l_i + 1$) 指定一条审美规则（要求），各数之间由单个空格分隔。这样的三元组要求链中编号为 $\{a_i, \dots, a_i + l_i - 1\}$ 的片段与编号为 $\{b_i, \dots, b_i + l_i - 1\}$ 的片段必须完全相同。换句话说，编号为 $a_i$ 和 $b_i$ 的灯必须颜色相同，编号为 $a_i + 1$ 和 $b_i + 1$ 的灯也必须颜色相同，以此类推，直到编号为 $a_i + l_i - 1$ 和 $b_i + l_i - 1$ 的灯。

输出格式

你的程序应向标准输出打印一个正整数 $k$：在满足输入给定的审美要求的前提下，一串彩灯中可能出现的最大不同颜色数量。

样例

样例输入 1

10 3
1 6 3
5 7 4
3 8 1

样例输出 1

3

样例输入 2

4 2
1 2 2
2 3 2

样例输出 2

1

说明

第一个样例的解释：令 $a, b$ 和 $c$ 表示三种不同的灯光颜色。那么以下彩灯串满足 Byteasar 和他妻子的要求：abacbababa。

子任务

测试集由以下指定的具有特定属性的子集组成。每个子集内可能包含多个测试组。