K. Shopping Quest
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Edward is shopping in Homs. There are $$$n$$$ shops arranged in a row, and shop $$$i$$$ sells one item with price $$$a_i$$$.

The street has two entrances:

  • the left entrance, located before shop $$$1$$$;
  • the right entrance, located after shop $$$n$$$.

Initially, Edward stands outside the left entrance and has $$$k$$$ money.

Edward starts from the left entrance. He may buy a prefix of items:

$$$$$$ \left[a_1, a_2, \ldots, a_x\right] $$$$$$

where $$$0 \le x \le n$$$. The prefix is allowed to be empty.

After that, Edward may switch entrances at most once. If he switches, he enters from the right entrance and buys a suffix of items in the following order:

$$$$$$ \left[a_n, a_{n-1}, \ldots, a_{n-y+1}\right] $$$$$$

where $$$0 \le y \le n-x$$$. The suffix is allowed to be empty.

Therefore, for some $$$x$$$ and $$$y$$$, Edward buys items in the exact order:

$$$$$$ \left[a_1, a_2, \ldots, a_x, a_n, a_{n-1}, \ldots, a_{n-y+1}\right] $$$$$$

The shop owner gives Edward $$$d$$$ coupons.

Before buying an item, Edward may use one unused coupon on it. If he does, the item's price becomes $$$0$$$, and Edward can buy it without spending any money.

Each coupon can be used on at most one item, and each item can be bought at most once.

Before buying an item without using a coupon, Edward must have at least its price. After buying it, his amount of money decreases by its price. Note that if an item's price is negative, buying it increases Edward's money.

Find the maximum number of items Edward can buy without ever being unable to afford an item.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$d$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^{16}$$$, $$$1 \le d \le 20$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$), where $$$a_i$$$ is the price of the item in shop $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the maximum number of items Edward can buy.

Example
Input
3
6 5 1
4 -10 50 50 -2 3
5 75 1
90 100 -1000 100 90
4 4 1
7 8 -4 7
Output
5
1
3