题目描述

Bob 喜欢在手机上玩一个有趣的塔防游戏。在游戏中，他需要出牌来击败对手！

有 $n$ 张牌，按顺序排成一个队列，称为牌堆。在任何时刻，Bob 只能从牌堆的前 $k$ 张牌中出牌。每一回合，Bob 选择一张当前位于前 $k$ 的牌，将其从牌堆中移除，使用后再把同一张牌放到牌堆的末尾。也就是说，每回合，从队首前 $k$ 张牌中选择一张，将其移到队列的末尾，其后的所有元素前移一位。

有一张特殊的牌称为“胜利条件牌”，Bob 想要尽可能多地使用这张牌。但每张牌的使用需要消耗一定的能量。初始时，在第 $i$ 个位置（即 $i$ 从 1 开始计数）的牌使用一次需消耗 $a_i$ 的能量。所有出牌消耗的总能量不能超过 $m$。胜利条件牌最初位于牌堆的第 $p$ 个位置。

你需要计算出，在总能量不超过 $m$ 的前提下，胜利条件牌最多能被使用多少次。

输入格式

输入包含多组测试用例。第一行是测试用例个数 $t$（$1\le t\le 5000$）。接下来分别为每组测试用例的数据：

每组测试用例的第一行为四个整数 $n, k, p, m$（$1\le k, p\le n\le 5000$，$1\le m\le 5000$），分别表示牌的数量、每次可选择的出牌范围、胜利条件牌初始位置及总能量。

第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每张牌每次使用所需的能量（$1\le a_i\le m$）。

保证所有测试用例的 $n$ 之和不超过 $5000$。

输出格式

每个测试用例输出一行，表示胜利条件牌能被使用的最大次数。

说明/提示

在第一个测试用例中，你只能出队首第一张牌，而出这张牌就用光了所有能量。由于胜利条件牌在队列的第二位，在能量用尽前无法出牌，所以答案为 $0$。

在第二个测试用例中，可以出队列中的任何一张牌。最优策略很显然只会出胜利条件牌。由于每次用这张牌消耗 $1$ 能量，总共有 $6$ 能量，因此能最多使用 $6$ 次。答案为 $6$。

第三个测试用例中，可以如下操作（胜利条件牌用红色标记）：

初始队列为 $[2, \color{red}{1}, 2]$。

出队首第一张牌：队列变为 $[\color{red}{1}, 2, 2]$。

再次出队首第一张牌：队列变为 $[2, 2, \color{red}{1}]$。

再次出队首第一张牌：队列变为 $[2, \color{red}{1}, 2]$。

出队首第二张牌：队列变为 $[2, 2, \color{red}{1}]$。

在此过程中，胜利条件牌共被使用了 $2$ 次，总共消耗了 $6$ 能量。可以证实，不存在其它方案能在消耗不超过 $6$ 的情况下多用一次胜利条件牌，因此答案为 $2$。

第四个测试用例中，可以证实最多只能用一次胜利条件牌。始终选择队列中第 $4$ 张牌即可实现，答案为 $1$。

由 ChatGPT 5 翻译

样例

4
2 1 2 42
42 1
3 3 2 6
2 1 2
3 2 2 6
2 1 2
8 4 7 10
3 4 4 2 1 1 4 2

0
6
2
1