题目内容

多多是一个大模型架构师，在部署大语言模型时为了提高 $GPU$ 的利用率，推理引擎通常会将多个用户的请求合并成一个批次进行并行计算。同一批次内如果请求长度不同，短请求会被填充空白 $Token$ 补到该批次最长请求的长度。

为了在“高并发”和“少浪费”之间取得平衡，多多制定了如下的批处理调度策略：

1. 显存限制：每个批次最多只能包含 $C$ 个请求。
2. 算力浪费限制：同一个批次内，最长请求的 $Token$ 数与最短请求的 $Token$ 数之差不能超过 $K$。
3. 请求的执行顺序可以被任意打乱。

在实际业务中，偶尔会出现极个别长度异常的“离群”请求。为了不让这些离群点拖累整体吞吐量，系统引入了降级策略：推理引擎最多允许直接丢弃 $M$ 个请求，被丢弃的请求可以不处理。

现在，服务器积压了 $N$ 个请求，第 $i$ 个请求包含 $L_i$ 个Token。请帮多多设计一个调度算法，在最多丢弃 $M$ 个请求的前提下，最少需要将剩下的请求划分成多少个批次？

输入描述

第一行包含一个整数 $T(1 \le T \le 3)$，表示测试用例的数量。

对于每个测试用例：

第一行包含四个整数 $N,\ M,\ K,\ C$，分别表示请求总数、最多允许丢弃的请求数、允许的最大长度差、单个批次最大请求数。

$1 \le N \le 10^5,\ 0 \le M \le 50,\ 0 \le K \le 10^9,\ 1 \le C \le N$

第二行包含 $N$ 个整数 $L_1,L_2,\dots,L_n$，表示每个请求的 $Token$ 长度。

$1 \le L \le 10^9$

输出描述

对于每个测试用例，输出一行包含一个整数，表示最少需要的批次数量。

样例1

输入

2
5 1 1 2
10 11 15 16 17
4 2 10 3
1 100 2 200

输出

2
1

说明

第一个样例 $N$=$5$,$M$=$1$,$K$=$1$,$C$=$2$，长度为 $[10, 11, 15, 16, 17]$。

如果不丢弃任何请求，至少需要 $3$ 个批次（例如 $(10, 11), (15, 16), (17)$）。

如果允许丢弃 $1$ 个请求，我们可以选择丢弃 $15$，剩下的 $(10, 11)$ 编为一批，最大差值为 $1$；$(16, 17)$ 编为一批，最大差值为 $1$，此时只需要 $2$ 个批次。

第二个样例 $N$=$4$,$M$=$2$,$K$=$10$,$C$=$3$，长度为 $[1, 100, 2, 200]$。

丢弃离群点 $100$ 和 $200$，剩下 $(1, 2)$ 可以放在一个批次中，因此最少需要 $1$ 个批次。