题目内容

在大语言模型（LLM）的自回归推理中，为了避免重复计算历史 Token 的注意力键值，系统会为每个请求维护一份 KV 缓存（Key-Value Cache）。缓存要占用显存，而显存总量是固定的；同一时刻能并行推进的请求越多，整体吞吐就越高。本题要求你在容量允许的范围内，按系统给定的规则把请求排进每个时间步，并算出全部请求处理完毕所用的总时间步数。

请求与显存

时间窗口内共有 $N$ 个请求，第 $i$ 个请求用三个整数描述：

• $arrive_i$：请求到达系统的时刻（时间步从 $0$ 开始编号）；
• $tokens_i$：该请求还需要生成的 Token 个数；
• $mem_i$：处理该请求时，其 KV 缓存占用的显存单位数；被处理期间每生成一个 Token 都占用这么多显存，占用大小不随进度变化。

系统可用的显存总容量为 $M$ 个单位。

处理规则

1. 并行处理：每个时间步，系统可以把显存分配给若干「已到达且尚未完成」的请求，让它们各自生成 $1$ 个 Token。同一个请求在同一个时间步最多生成 $1$ 个 Token，不允许靠多占缓存来提速。被分配显存的请求，其 $mem_i$ 之和不能超过 $M$。
2. 完成与释放：某个请求累计被处理满 $tokens_i$ 个时间步后即完成；完成的那一刻立刻释放它占用的显存，释放出来的显存从下一个时间步起才能分配给其他请求。
3. 接纳顺序：系统事先看不到请求还剩多少 Token，因此采用固定的贪心策略。每个时间步，在所有「已到达、未完成、尚未占住显存」的请求中，先按 $mem_i$ 从小到大挑选，$mem_i$ 相同则到达更早的请求优先；按这个顺序依次尝试分配显存，装得下就接纳，装不下就让它继续等待。系统不会拒绝一个装得下的请求。已经被接纳的请求会一直处理到完成。
4. 缓存清空：系统也允许在某个时间步主动清空一个未完成请求的缓存，此时它已生成的 Token 数保留、显存立刻释放、该请求回到等待状态；但它重新开始时必须重新占用 $mem_i$ 显存，并且要先把已生成 Token 对应的计算时间重算一遍（即从被清空时的进度起重新累计计算时间）。清空只会让已经付出的计算时间作废，因此最优做法是不清空任何请求的缓存。

目标

按上述规则运行系统，输出全部请求处理完毕时最后一个请求完成的时刻，也就是所需的总时间步数。

输入描述

第一行包含两个整数 $N$ 与 $M$，依次表示请求数量与显存容量。

接下来 $N$ 行，每行包含三个整数 $arrive_i$、$tokens_i$、$mem_i$，依次描述一个请求。请求按从上到下的顺序先后到达，同一时刻只会有一个请求到达。

输出描述

输出一个整数，表示全部请求处理完毕所需的总时间步数。

约束条件

• $1 \le N \le 100$
• $1 \le M \le 1000$
• $0 \le arrive_i \le 1000$
• $1 \le tokens_i \le 100$
• $1 \le mem_i \le 100$
• 数据保证存在可行的调度方案，即每个请求都能被处理完。

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms 内存限制：C/C++ 512MB，其他语言：1024MB

样例 1

输入

3 6
0 5 4
1 4 4
2 3 2

输出

9

说明

请求 $1$ 在时刻 $0$ 到达，占用 $4$ 个单位的显存开始处理。时刻 $1$ 请求 $2$ 到达，此时 $4+4=8$ 已超过容量 $6$，只能等待；时刻 $2$ 请求 $3$ 到达，它的 $mem$ 为 $2$，比请求 $2$ 更小，于是优先获得 $4+2=6$ 的显存，与请求 $1$ 并行处理。请求 $1$ 用 $5$ 个时间步（时刻 $0$ 到 $4$）在时刻 $5$ 完成，请求 $3$ 用 $3$ 个时间步（时刻 $2$ 到 $4$）也在时刻 $5$ 完成，显存全部释放。请求 $2$ 从时刻 $5$ 起处理 $4$ 个时间步，于时刻 $9$ 完成。总时间步数为 $9$。

样例 2

输入

3 9
0 4 3
1 3 3
2 5 3

输出

7

说明

三个请求的 $mem$ 都为 $3$，总和 $3+3+3=9$ 不超过容量 $9$，因此可以同时处理。请求 $1$ 在时刻 $0$ 到达，用 $4$ 个时间步于时刻 $4$ 完成；请求 $2$ 在时刻 $1$ 到达，用 $3$ 个时间步于时刻 $4$ 完成；请求 $3$ 在时刻 $2$ 到达，用 $5$ 个时间步于时刻 $7$ 完成。最后一个请求在时刻 $7$ 完成，总时间步数为 $7$。