OtterZ set up a battle with $$$n$$$ monsters in order to increase his combat power. Each monster has a combat power $$$a_i$$$ and OtterZ has a combat power of $$$c$$$. He has $$$k$$$ flip flops and can perform the following operations:

Kill an alive monster $$$i$$$ if $$$a_i \le c$$$; then $$$c$$$ becomes $$$c + a_i$$$.
Throw a flip flop at an alive monster $$$i$$$; the flip-flop will be broken and the monster will become angrier, then $$$a_i$$$ becomes $$$a_i + 1$$$.

Help OtterZ obtain the maximum possible $$$c$$$ after the battle.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$c$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le c,k \le 10 ^ 9$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10 ^ 9$$$).

Output

For each test case, output an integer — the maximum possible combat power.

Note

In the first test,OtterZ found a strong monster and ran away, with combat power $$$12$$$.

In the sixth test, OtterZ participated in the battle:

Throw $$$10$$$ flip flops to monster $$$2$$$, the combat power of monster $$$2$$$ turns to $$$12$$$.
Throw $$$10$$$ flip flops to monster $$$1$$$, the combat power of monster $$$1$$$ turns to $$$11$$$.
Kill monster $$$1$$$, OtterZ's combat power turns to $$$29$$$.
Throw $$$10$$$ flip flops to monster $$$5$$$, the combat power of monster $$$5$$$ turns to $$$12$$$.
Kill monster $$$2$$$, OtterZ's combat power turns to $$$41$$$.
Kill monster $$$5$$$, OtterZ's combat power turns to $$$53$$$.
OtterZ runs away with combat power $$$53$$$.

Flip Flops

Examples