题目内容

在一个智能家居系统中，用户可以设置多个“自动化联动”模式。每个模式 $\text{modes}[i] = [\text{start\_time}, \text{end\_time}, \text{power}]$ 描述如下：

• 模式在左闭右开区间 $[\text{start\_time}, \text{end\_time})$（单位：秒）内处于运行状态
• 为了简化处理，$\text{start\_time}$、$\text{end\_time}$ 已转化为相对于系统启动初始时间点的秒数
• 运行期间，每秒消耗固定功率 $\text{power}$

已知家里电网的最高承受功率 $\text{max\_power}$。若同一时刻有多个模式同时运行，则总功率为各模式功率之和。如果总功率大于 $\text{max\_power}$，则会导致跳闸。

系统允许永久删除（关闭）任意若干个模式，使剩余模式在任意时刻同时运行时永不跳闸。

请你计算：最少需要删除多少个模式？

输入描述

• $\text{max\_power}$：整数代表用户电网能承受的最大总电功率，取值 $1 \le \text{max\_power} \le 10^6$
• $\text{modes}$：二维数组，每个子数组 $\text{modes}[i] = [\text{start\_time}, \text{end\_time}, \text{power}]$，表示第 $i$ 个智能模式的启动时间、结束时间以及运行它所需要的电功率。
  • $\text{start\_time}, \text{end\_time}$：取值 $0 \le \text{start\_time} < \text{end\_time} \le 10^5$
  • $\text{power}$：取值 $1 \le \text{power} \le 10^4$
  • 模式数量取值 $1 \le n \le 22$

输出描述

最少需要删除的模式个数

样例1

输入

10,[[0,500,5],[400,600,7],[550,700,4]]

输出

1

说明

• 最高承受功率 $\text{max\_power}$ 为 10
• 模式 0 在时间范围 $[0, 500)$ 运行，功率 5
• 模式 1 在时间范围 $[400, 600)$ 运行，功率 7
• 模式 2 在时间范围 $[550, 700)$ 运行，功率 4
• 在 $(400, 500)$ 区间内，模式 0 和 1 同时运行，功率 $5+7=12 > 10$，发生跳闸
• 删除 1 个模式即可避免（删除模式 1，保留 0 和 2）

样例2

输入

10,[[0,300,5],[400,600,7],[700,900,3]]

输出

0

说明

• 3 个模式时间上互不重叠，可同时安全运行

样例3

输入

10,[[0,10,6],[0,10,6]]

输出

1

说明

• 两个模式完全重叠，功率均为 6，同时运行为 $12 > 10$，必须删除一个