A. Шлёпки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

OtterZ устроил битву с $$$n$$$ монстрами, чтобы увеличить свою боевую мощь. У каждого монстра есть боевая мощь $$$a_i$$$, а у OtterZ — боевая мощь $$$c$$$. У него есть $$$k$$$ шлёпок, и он может выполнять следующие операции:

  1. Убить живого монстра $$$i$$$, если $$$a_i \le c$$$; тогда $$$c$$$ становится $$$c + a_i$$$.
  2. Бросить шлёпок в живого монстра $$$i$$$; шлёпок сломается, и монстр станет более злым, тогда $$$a_i$$$ станет $$$a_i + 1$$$.
Помогите OtterZ получить максимальное возможное $$$c$$$ после битвы.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$c$$$ и $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le c,k \le 10 ^ 9$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10 ^ 9$$$).

Выходные данные

Для каждого набора входных данных выведите целое число — максимальную возможную боевую мощь.

Пример
Входные данные
10
1 12 23
21
1 8 4
5
1 3 4
16
3 6 3
14 9 11
5 9 2
20 16 18 16 11
5 18 30
1 2 93 84 2
7 29 13
2 9 38 4 7 1 6
10 9 2
8 1 8 11 17 3 14 16 20 10
10 192 109
1 9 20 9 829 3 87 1 283 7
10 1000000000 1000000000
19 1000000000 1 9 2 3 8 1 2 3
Выходные данные
12
16
3
6
9
53
109
119
721
3000000048
Примечание

В первом наборе входных данных OtterZ наткнулся на слишком сильного монстра, он не совершает никаких операций и уходит с боевой мощью $$$12$$$.

В шестом наборе входных данных OtterZ участвовал в битве:

  1. Бросил $$$10$$$ шлёпков в монстра $$$2$$$, боевая мощь монстра $$$2$$$ становится $$$12$$$.
  2. Бросил $$$10$$$ шлёпков в монстра $$$1$$$, боевая мощь монстра $$$1$$$ становится $$$11$$$.
  3. Убил монстра $$$1$$$, боевая мощь OtterZ становится $$$29$$$.
  4. Бросил $$$10$$$ шлёпков в монстра $$$5$$$, боевая мощь монстра $$$5$$$ становится $$$12$$$.
  5. Убил монстра $$$2$$$, боевая мощь OtterZ становится $$$41$$$.
  6. Убил монстра $$$5$$$, боевая мощь OtterZ становится $$$53$$$.
  7. OtterZ уходит с боевой мощью $$$53$$$.