B. Cyclists
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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

Example
Input
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
Output
0
6
2
1
Note

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$$$.