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

Медуза установила бомбу в Сноудине!

Бомба оснащена таймером, который первоначально установлен на $$$b$$$. Каждую секунду таймер будет уменьшаться на $$$1$$$. Когда таймер достигнет отметки $$$0$$$, бомба взорвется! Чтобы дать жителям Сноудина достаточно времени для эвакуации, необходимо как можно дольше задержать взрыв бомбы.

У вас есть $$$n$$$ инструментов. Каждый инструмент может быть использован не более одного раза. Если Вы используете $$$i$$$-й инструмент, то таймер увеличится на $$$x_i$$$. Однако, если после изменения значение таймера становится больше $$$a$$$, то из-за ошибки таймер будет установлен на $$$a$$$.

Более конкретно, каждую секунду будут происходить следующие события в следующем порядке:

  1. Вы выберете некоторые (возможно, ни одного) из своих инструментов, которые не использовались ранее. Если вы выбрали $$$i$$$-й инструмент, а таймер бомбы в данный момент установлен на $$$c$$$, то таймер будет изменен на $$$\min(c + x_i, a)$$$.
  2. Таймер уменьшается на $$$1$$$.
  3. Если таймер достигнет $$$0$$$, бомба взорвется.

Теперь Медуза хочет узнать максимальное время в секундах до взрыва бомбы при оптимальном использовании инструментов.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$a$$$, $$$b$$$ и $$$n$$$ ($$$1 \leq b \leq a \leq 10^9$$$, $$$1 \leq n \leq 100$$$) — максимальное значение таймера бомбы, начальное значение таймера бомбы и количество инструментов.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) — число, на которое может увеличиться таймер при использовании $$$i$$$-го инструмента.

Следует отметить, что сумма $$$n$$$ по всем наборам входных данных не ограничена.

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

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

Пример
Входные данные
2
5 3 3
1 1 7
7 1 5
1 2 5 6 8
Выходные данные
9
21
Примечание

Пусть $$$c$$$ обозначает значение таймера бомбы. В первом наборе входных данных:

  • Секунда $$$1$$$: выбираем инструменты $$$1$$$ и $$$2$$$ в эту секунду, получаем $$$c=5$$$; таймер уменьшается на $$$1$$$, получаем $$$c=4$$$.
  • Секунда $$$2$$$: таймер уменьшается на $$$1$$$, получаем $$$c=3$$$.
  • Секунда $$$3$$$: таймер уменьшается на $$$1$$$, получаем $$$c=2$$$.
  • Секунда $$$4$$$: таймер уменьшается на $$$1$$$, получаем $$$c=1$$$.
  • Секунда $$$5$$$: выбераем инструмент $$$3$$$, получаем $$$c=5$$$; таймер уменьшается на $$$1$$$, получаем $$$c=4$$$.
  • Секунда $$$6$$$: таймер уменьшается на $$$1$$$, получаем $$$c=3$$$.
  • Секунда $$$7$$$: таймер уменьшается на $$$1$$$, получаем $$$c=2$$$.
  • Секунда $$$8$$$: таймер уменьшается на $$$1$$$, получаем $$$c=1$$$.
  • Секунда $$$9$$$: таймер уменьшается на $$$1$$$, получаем $$$c=0$$$. Бомба взрывается.

Можно показать, что не существует способа использовать инструменты так, чтобы бомба взорвалась более чем через $$$9$$$ секунд.