题目描述

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

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

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

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

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 第一行输入四个整数 $n, k, p, m$，分别表示牌的数量、每次可选择的出牌范围、胜利条件牌初始位置及总能量。
• 第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每张牌每次使用所需的能量。

输出格式

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

5
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
2 1 2 2
1 1

0
6
2
1
1

提示

样例解释

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

数据范围

对于 $100\%$ 的数据满足：$1\le t\le 5000$，$1\le k, p\le n\le 5000$，$1\le m\le 5000$，$1\le a_i\le m$，保证所有测试用例的 $n$ 之和不超过 $5000$。

• 子任务 1 (20分)：$k = n$。
• 子任务 2 (30分)：$n \le 10$。
• 子任务 3 (50分)：无特殊限制。