题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — II etap Świąteczny łańcuch

每年圣诞节，Bajtazar 都会用五彩缤纷的灯链装点他的家。今年，他决定亲自挑选灯链的颜色，打造一串独一无二的装饰。他对灯链的美学有特定要求：某些灯链片段的颜色排列需与另一些片段完全相同。同时，他的妻子希望今年的灯链尽量丰富多彩，也就是说，灯链应包含尽可能多的不同颜色。请帮助 Bajtazar 计算，他需要购买多少种颜色的灯泡。

输入格式

第一行包含两个整数 $n, m$ $(n \geq 2, m \geq 1)$，分别表示灯链中灯泡的数量和 Bajtazar 的美学要求数量。灯泡按顺序编号为 $1$ 至 $n$。

接下来的 $m$ 行描述美学要求，每行包含三个整数 $a_i, b_i, l_i$ $(1 \leq a_i, b_i, l_i; a_i \neq b_i; a_i, b_i \leq n - l_i + 1)$，表示灯链片段 $\{a_i, \ldots, a_i + l_i - 1\}$ 和 $\{b_i, \ldots, 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$，表示满足所有美学要求时，灯链中可包含的最大不同颜色数。

10 3
1 6 3
5 7 4
3 8 1

3

4 2
1 2 2
2 3 2

1

提示

样例 1 解释

设 $a, b, c$ 表示三种不同颜色的灯泡。一个满足 Bajtazar 及其妻子要求的灯链为 $\texttt{abacbababa}$。

附加样例

1. $n=2000, m=2$，要求片段 $\{1, \ldots, 1000\}$ 与 $\{1001, \ldots, 2000\}$ 相同，$\{1, \ldots, 500\}$ 与 $\{501, \ldots, 1000\}$ 相同，最大颜色数为 $500$。
2. $n=500000, m=499900$，第 $i$ 个要求为 $a_i=i, b_i=i+100, l_i=1$，最大颜色数为 $100$。
3. $n=80000, m=79995$，第 $i$ 个要求为 $a_i=i, b_i=i+2, l_i=4$，最大颜色数为 $2$。
4. $n=50000, m=25000$，第 $i$ 个要求为 $a_i=1, b_i=i+1, l_i=9$，灯链只能使用单一颜色。

详细子任务附加限制及分值如下表所示。