题目内容

某新能源公司有 $N$ 个充电桩和 $M$ 辆电动车需要充电。每辆车有一个预计到达时间和需要的充电时间。每辆车有预计到达时间$AT$、需要的充电时间$CT$、最大可等待时长$WT$（从到达后到开始充电的等待时间不能超过该值，否则车辆会离开，无法完成充电）。

为了最大化充电桩利用率，需要设计调度算法，使得尽可能多的车辆能够按时完成充电。

规则

• 每个充电桩同一时间只能服务一辆车；
• 车辆必须在其预计到达时间或之后开始充电；
• 一旦开始充电就不能中断；
• 车辆从到达后到开始充电的等待时间 $=$ 开始充电时间 $-$ 到达时间，该值必须 $≤$ 车辆的最大可等待时长，否则车辆无法充电；
• 目标是最小化未能按时完成充电的车辆数量（包括等待超时离开的车辆）。
• 车辆到达场站后，若有充电桩空闲则立即充电，如果没有充电桩，则等待出现空闲充电桩后，先到的车辆先进行充电。

输入描述

输入包含一行数据，格式：$N$,$M$,[$AT1$,$CT1$,$WT1$],[$AT2$,$CT2$,$WT2$],……,[$ATM$,$CTM$,$WTM$]

• 整数 $N$ 表示充电桩数量；
• 整数 $M$ 表示车辆数量；
• $M$ 个一维数组[$AT1$,$CT1$,$WT1$]……[$ATM$,$CTM$,$WTM$]，表示每辆车的到达时间 $AT$、充电时间 $CT$、最大可等待时长 $WT$；

约束条件：

• $1 ≤ N ≤ 100$，$1 ≤ M ≤ 1000$，
• $1 ≤ AT ≤ 10000$，$1 ≤ CT ≤ 10000$，$0 ≤ WT ≤ 10000$，
• 不考虑最大可等待时长 $WT$ 过长的合理性

输出描述

充电失败的车辆数量

样例1

输入

3,5,[[10,1,0],[10,1,0],[10,1,0],[10,1,0],[10,1,0]]

输出

2

说明

• $3$ 个充电桩
• $5$ 辆汽车
• $10$ $1$ $0$ // 车辆 $1$：到达 $10$，充电 $1$，最多等 $0$（必须立即开始）
• $10$ $1$ $0$ // 车辆 $2$：到达 $10$，充电 $1$，最多等 $0$（必须立即开始）
• $10$ $1$ $0$ // 车辆 $3$：到达 $10$，充电 $1$，最多等 $0$（必须立即开始）
• $10$ $1$ $0$ // 车辆 $4$：到达 $10$，充电 $1$，最多等 $0$（必须立即开始）
• $10$ $1$ $0$ // 车辆 $5$：到达 $10$，充电 $1$，最多等 $0$（必须立即开始）

车辆 $1$ 时刻 $10$ 到达，占用充电桩 $1$ 进行充电，充电开始时间为 $10$，充电时长为 $1$，等待时间为 $0$，充电结束时间为 $11$，即充电桩 $1$ 释放时刻为 $11$，车辆 $1$ 充电成功。

车辆 $2$ 时刻 $10$ 到达，充电桩 $2$ 为空闲，充电开始时间为 $10$，充电时长为 $1$，充电结束时间为 $11$，即充电桩 $2$ 释放时刻为 $11$，车辆 $2$ 充电成功。

车辆 $3$ 时刻 $10$ 到达，充电桩 $3$ 为空闲，充电开始时间为 $10$，充电时长为 $1$，充电结束时间为 $11$，即充电桩 $3$ 释放时刻为 $11$，车辆 $3$ 充电成功。

车辆 $4$ 时刻 $10$ 到达，充电桩 $1$ $2$ $3$ 在 $10$ 时刻均为占用状态，车辆 $4$ 等待时间为 $0$，必须立即充电，此时无充电桩空闲，因此车辆 $4$ 充电失败。

车辆 $5$ 时刻 $10$ 到达，充电桩 $1$ $2$ $3$ 在 $10$ 时刻均为占用状态，车辆 $5$ 等待时间为 $0$，必须立即充电，此时无充电桩空闲，因此车辆 $5$ 充电失败。

综上分析，车辆 $4$ $5$ 充电失败，输出为 $2$。

样例2

输入

2,4,[[1,10,0],[2,2,1],[3,1,0],[4,1,0]]

输出

1

说明

• $2$ 个充电桩
• $4$ 辆汽车
• $1$ $10$ $0$ // 车辆 $1$：到达 $1$，充电 $10$，最多等 $0$（必须立即开始）
• $2$ $2$ $1$ // 车辆 $2$：到达 $2$，充电 $2$，最多等 $1$（开始充电时间 $≤3$）
• $3$ $1$ $0$ // 车辆 $3$：到达 $3$，充电 $1$，最多等 $0$（必须立即开始）
• $4$ $1$ $0$ // 车辆 $4$：到达 $4$，充电 $1$，最多等 $0$（必须立即开始）

车辆 $1$ 先到占用充电桩 $1$ 进行充电，充电开始时间为 $1$，充电时长为 $10$，充电结束时间为 $11$，即充电桩 $1$ 释放时刻为 $11$，车辆 $1$ 充电成功。

车辆 $2$ 时刻 $2$ 到达，充电桩 $2$ 为空闲，充电开始时间为 $2$，充电时长为 $2$，充电结束时间为 $4$，即充电桩 $2$ 释放时刻为 $4$，车辆 $2$ 充电成功。

车辆 $3$ 时刻 $3$ 到达，$3$ 时刻没有充电桩空闲，可以等待时间为 $0$，即 $3$ 时刻必须进行充电，但是 $3$ 时刻充电桩 $1$ 充电桩 $2$ 都还没有释放，车辆 $3$ 充电失败。

车辆 $4$ 时刻 $4$ 到达，$4$ 时刻充电桩 $2$ 已经释放，车辆 $4$ 可以正常充电，车辆 $4$ 充电成功。

综上分析，只有车辆 $3$ 充电失败，输出为 $1$。