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). 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). For each test case, output one integer in one line, denoting the maximum times the win-condition can be play