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:

1. Kill an alive monster $i$ if $a_i \le c$; then $c$ becomes $c + a_i$.
2. 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:

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