600. K for the Price of One
0
Hard
This is the challenging version of the problem. The only difference lies in the constraint on k, which represents the number of gifts in the offer.
Vasya has come to a store to purchase goods for his friends for the New Year. Fortunately, today the store is running a special offer called "k for the price of one".
Under this offer, Vasya can buy exactly k items of any goods, but he only needs to pay for the most expensive item. Vasya wants to take full advantage of this opportunity and buy as many goods as possible for his friends with the money he has.
To clarify, each good has a price ai, which represents the number of coins required to purchase it. Initially, Vasya has p coins. His goal is to maximize the number of goods he can buy. Vasya can perform the following operations as many times as needed:
1. Buy one good with the index i if he has enough coins (i.e., p≥ai). After the purchase, the number of Vasya's coins will decrease by ai (i.e., p:=p−ai).
2. Buy a good with the index i and also select exactly k-1 goods, whose prices do not exceed ai, if he has enough coins (i.e., p≥ai). In this case, he buys all k goods and his number of coins decreases by ai (i.e., p:=p−ai).
It is important to note that each good can only be bought once.
For example, if the store currently has n=5 goods with prices a1=2, a2=4, a3=3, a4=5, and a5=7, and Vasya has 6 coins, he can buy a maximum of 3 goods. Vasya will buy the good with index 1 without using the offer and pay 2 coins. He will use the offer to buy the goods with indices 2 and 3, paying 4 coins. It can be proven that Vasya cannot buy more goods with 6 coins.
Assist Vasya in determining the maximum number of goods he can purchase.
Input Format
The first line contains an integer t, which represents the number of test cases.
The following lines provide a description of t test cases.
Each test case begins with a line containing three integers n, p, and k. These represent the number of goods in the store, the number of coins Vasya has, and the number of goods that can be purchased for the price of the most expensive item, respectively.
The second line of each test case contains n integers ai, which represent the prices of the goods. It is guaranteed that the sum of n for all test cases does not exceed 2⋅105.
Output Format
For each test case, print a single integer m on a separate line. This represents the maximum number of goods that Vasya can purchase.
Example
Input
8
5 6 2
2 4 3 5 7
5 11 2
2 4 3 5 7
3 2 3
4 2 6
5 2 3
10 1 3 9 2
2 10000 2
10000 10000
2 9999 2
10000 10000
4 6 4
3 2 3 2
5 5 3
1 2 2 1 2
Output
3
4
1
1
2
0
4
5
Constraints
1≤t≤104
1≤ai≤104
2≤n≤2⋅105
1≤p≤2⋅109
2≤k≤n
1≤ai≤104
2≤n≤2⋅105
1≤p≤2⋅109
2≤k≤n
Loading...
View Submissions
Console