Gift Shop and Coupon

 Chef wants to impress Chefina by giving her the maximum number of gifts possible.

Chef is in a gift shop having N$N$ items where the cost of the ith$i^{th}$ item is equal to Ai$A_i$. Chef has K$K$ amount of money and a 50%$50\mathrm{\%}$ off discount coupon that he can use for at most one of the items he buys.

If the cost of an item is equal to X$X$, then, after applying the coupon on that item, Chef only has to pay ⌈X2⌉$\lceil \frac{\mathbf{X}}{\mathbf{2}}\rceil$ (rounded up to the nearest integer) amount for that item.

Help Chef find the maximum number of items he can buy with K$K$ amount of money and a 50%$50\mathrm{\%}$ discount coupon given that he can use the coupon on at most one item.

Input Format

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and K$K$.
• The next line contains N$N$ space-separated integers, where the ith$i^{th}$ integer Ai$A_i$ denotes the cost of the ith$i^{th}$ item.

Output Format

For each test case, print a single line containing one integer ― the maximum number of items Chef can buy.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$
• 0≤K≤109$0\le K\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

3
1 4
5
3 15
4 4 5
3 10
6 7 4

Sample Output 1 

1
3
2

Explanation

Test case 1$1$: After applying the discount, Chef can buy the only available item at ⌈52⌉=3$\lceil \frac{5}{2}\rceil =3$.

Test case 2$2$: Chef can buy all three items even without using the coupon.

Test case 3$3$: After applying coupon on the third item, Chef can buy the second and the third item at 7+⌈42⌉=$7+\lceil \frac{4}{2}\rceil =$ 7+2=9$7+2=9$.

• Tweet
• Share
• Share
• Share
• Share

Related Post