CF2208B.Cyclists

Bob likes to play an interesting tower defense game on his mobile phone. In the game, he must play cards to defeat his opponents!

There are $n$ cards placed in a queue called a deck. At any moment, Bob is only able to play the cards that are currently placed in the first $k$ positions in the deck. In each turn, Bob selects a card placed in the first $k$ positions, removes it from the deck, plays it, and then places the same card back at the bottom of the deck. In other words, in each turn an element from the first $k$ elements in the queue is selected, moved to the end of the queue, and all elements placed after it are moved one index to the front.

One card is called the win-condition, and Bob wants to play it as many times as possible. However, each card also has a cost needed to play. The $i$-th card (initially placed at the $i$-th position) costs Bob $a_i$ energy every time it is played. The total cost of cards played must not exceed $m$. Initially, the win-condition card is placed at the $p$-th place in the queue.

You need to find out the maximum number of times the win-condition card can be played, ensuring that the total cost does not exceed $m$.

鲍勃喜欢在手机上玩一款有趣的塔防游戏。在游戏中，他必须出牌来击败对手！

一共有 $n$ 张牌排成一列，称为“牌堆”。在任意时刻，鲍勃只能从牌堆最前面的 $k$ 张牌中选择一张进行出牌。每回合，鲍勃从当前牌堆最前面的 $k$ 张牌中选定一张，将其从牌堆中移除并打出，然后将这张牌放回牌堆末尾。换言之，每回合从队列的前 $k$ 个元素中选出一个元素，将其移动至队列末尾，而该元素之后的所有元素均向前移动一位。

其中有一张牌被称为“胜利条件牌”，鲍勃希望尽可能多地打出这张牌。然而，每张牌每次打出均需消耗一定能量（即有对应代价）。第 $i$ 张牌（初始时位于第 $i$ 个位置）每次打出消耗鲍勃 $a_i$ 点能量。所有已打出牌的总能量消耗不得超过 $m$。初始时，“胜利条件牌”位于队列中的第 $p$ 个位置。

你需要求出：在总能量消耗不超过 $m$ 的前提下，鲍勃最多能打出多少次“胜利条件牌”。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains four integers $n,k,p,m$ ($1\le k,p\le n\le 5000$, $1\le m\le 5000$), denoting the number of cards, the number of cards that are playable at a time, the initial position of the win-condition, and the total energy available.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le m$) denoting the cost of each card.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output one integer in one line, denoting the maximum times the win-condition can be played.

对于每个测试用例，在一行中输出一个整数，表示获胜条件最多可以触发的次数。

In the first test case, we can only play the first card in the deck, and playing it will use all the energy. Since the win-condition is the second card, we can't play it before energy runs out. Therefore, the answer is $0$.

In the second test case, we can play all the cards in the deck. The optimal strategy is obviously only playing the win-condition. Since it costs $1$ energy to play and we have $6$ energy in total, we can play it $6$ times before energy runs out. Therefore, the answer is $6$.

In the third test case, we can play cards as follows: (the win condition is colored red)

The initial deck is $[2,\color{red}{1},2]$.

Play the first card: The deck becomes $[\color{red}{1},2,2]$.

Play the first card again: The deck becomes $[2,2,\color{red}{1}]$.

Play the first card once again: The deck becomes $[2,\color{red}{1},2]$.

Play the second card: The deck becomes $[2,2,\color{red}{1}]$.

In the process, we have played the win-condition for $2$ times, and we used $6$ energy in total. It can be shown that no strategy allows us to play the win-condition more than $2$ times with no more than $6$ points of energy; therefore, the answer is $2$.

In the fourth test case, it can be shown that we can play the win-condition no more than once. This is achievable by always playing the $4$-th card in the deck. Therefore, the answer is $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$ 次；故答案为 $2$。

在第四个测试用例中，可以证明：获胜条件牌最多只能被打出 $1$ 次。该结果可通过始终打出牌堆中的第 $4$ 张牌来实现。故答案为 $1$。