大语言模型自回归生成时，历史 token 的 Key 与 Value 会缓存在 KV Cache 里，后面每一步解码直接复用，不必重算。序列越长，KV Cache 占的显存越多，而且是线性增长。

工程上通常先把显存切成一堆等大的块（Block）集中管理，这套机制叫内存池（Memory Pool）：Block 一次分配好，每个 Block 装固定条数 token 的 KV 数据。

题目描述

内存池中有 $m$ 个等大的 Block，每个 Block 能容纳 $k$ 条 token 的 KV 数据。

现有 $n$ 个推理请求，第 $i$ 个请求要处理 $len[i]$ 条 token（输入长度与生成长度之和），它占用的 Block 数为 $ceil(len[i]/k)$。

决策规则

1. 请求按给定顺序逐个到达。
2. 对每个请求可以选择接受或拒绝：
   • 接受：被接受请求占用的 Block 总数最终不能超过 $m$；
   • 拒绝：该请求不占用任何资源。
3. 允许在后续决策中撤销先前已接受的请求（释放它占用的 Block），以换取更好的整体结果。
4. 请求一旦被拒绝，就不能再次考虑。
5. 请求之间不允许重排，必须按到达顺序逐个决策。

优化目标

在接受的请求占用 Block 总数不超过 $m$ 的前提下，使被接受的请求数量最多。

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms

内存限制：C/C++ 512MB，其他语言：1024MB

输入格式

第一行三个整数 $m$、$k$、$n$，相邻两数之间用一个空格分隔。

第二行 $n$ 个整数，依次是 $len[1], len[2], \dots, len[n]$。

其中：

• $m$：内存池中的 Block 总数；
• $k$：每个 Block 能容纳的 token 条数；
• $n$：请求数量；
• $len[i]$：第 $i$ 个请求要处理的 token 条数。

输出格式

输出一个整数，表示最多可接受的请求数量。不要输出多余的空格或空行。

样例1

输入

4 8 3
20 6 11

输出

2

解释：三个请求的 Block 需求依次为 $ceil(20/8)=3$、$ceil(6/8)=1$、$ceil(11/8)=2$。只接第 1 个请求，它独占 3 个 Block，剩下 1 个 Block 哪个请求都放不下，只能接受 1 个；跳过它、改接第 2 与第 3 个请求，占用 $1+2=3$ 个 Block，可以接受 2 个。三个请求全接需要 $3+1+2=6$ 个 Block，超过上限 $4$，所以最多接受 2 个。

样例2

输入

6 9 4
7 22 13 10

输出

3

解释：每个 Block 装 9 条 token，四个请求的 Block 需求如下：

挑选需求最小的三个请求（第 1、3、4 个），占用 $1+2+2=5$ 个 Block，不超过 6，共接受 3 个；四个全接受需要 $1+3+2+2=8$ 个 Block，超过上限，所以最多接受 3 个。

提示

$1 \le m \le 100000$

$1 \le k \le 1000$

$1 \le n \le 100000$

$1 \le len[i] \le 1000000$

• 若某个请求需要的 Block 数超过 $m$，它一定无法被接受。
• 请求顺序不能改变，但后续决策中可以撤销先前的选择。
• 建议设计时间复杂度优于 $O(n^2)$ 的算法。