Problem Description

传感器部署

题目描述

某个线性监控系统需要沿一条走廊部署传感器。走廊被划分成 $n$ 个检测区，依次编号为 $1, 2, \dots, n$，每个检测区大小为 1 个单位，且最多只能安装一台传感器。

系统中共有 $h$ 条检测需求，第 $i$ 条需求用三个整数 $b_i, e_i, t_i$ 描述，表示第 $i$ 段监控范围要求：在编号区间 $[b_i, e_i]$（含两端）内，至少要有 $t_i$ 台传感器处于工作状态。

各条需求的监控范围可以互相重叠。同一台传感器安装在某个检测区后，可以被所有覆盖该区的需求同时统计。请你求出：能满足全部需求所需安装的最少传感器数量。

输入格式

输入的第一行是一个整数，代表检测区的个数 $n$。

输入的第二行是一个整数，代表需求条数 $h$。

第 $3$ 到第 $(h+2)$ 行，每行三个整数，第 $(i+2)$ 行的整数依次为 $b_i, e_i, t_i$，代表第 $i$ 条需求要求区间 $[b_i, e_i]$ 内至少有 $t_i$ 台传感器。

输出格式

输出一行一个整数，代表最少的传感器数量。

输入输出与文件要求

本题为文件输入输出（IO 赛制），必须使用 freopen 重定向，不能只使用标准输入输出。 请在 main 函数开头写上：

freopen("sensor.in", "r", stdin);    // 文件输入
freopen("sensor.out", "w", stdout);  // 文件输出

样例

样例 1

输入

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

输出

5

提示

样例 1 说明

一种最优方案是在检测区 $3, 4, 6, 8, 9$ 各装一台传感器，共 $5$ 台：需求 $[1,4]$ 内有 $2$ 台（$3, 4$），需求 $[4,6]$ 内有 $2$ 台（$4, 6$），需求 $[8,9]$ 内有 $2$ 台（$8, 9$），需求 $[3,5]$ 在补装检测区 $5$ 后也有 $2$ 台（$3, 4$）。可以证明 $4$ 台无法满足全部需求。

评测方式

本题使用文件输入输出：评测时会把测试数据放到程序运行目录下的 sensor.in， 并读取程序生成的 sensor.out。请确认你的程序在没有任何标准输入的情况下也能正确运行。

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \le n \le 3 \times 10^4$，$1 \le h \le 5 \times 10^3$；
• $1 \le b_i \le e_i \le n$，$1 \le t_i \le e_i - b_i + 1$。