Медуза установила бомбу в Сноудине!
Бомба оснащена таймером, который первоначально установлен на \(b\). Каждую секунду таймер будет уменьшаться на \(1\). Когда таймер достигнет отметки \(0\), бомба взорвется! Чтобы дать жителям Сноудина достаточно времени для эвакуации, необходимо как можно дольше задержать взрыв бомбы.
У вас есть \(n\) инструментов. Каждый инструмент может быть использован не более одного раза. Если Вы используете \(i\)-й инструмент, то таймер увеличится на \(x_i\). Однако, если после изменения значение таймера становится больше \(a\), то из-за ошибки таймер будет установлен на \(a\).
Более конкретно, каждую секунду будут происходить следующие события в следующем порядке:
- Вы выберете некоторые (возможно, ни одного) из своих инструментов, которые не использовались ранее. Если вы выбрали \(i\)-й инструмент, а таймер бомбы в данный момент установлен на \(c\), то таймер будет изменен на \(\min(c + x_i, a)\).
- Таймер уменьшается на \(1\).
- Если таймер достигнет \(0\), бомба взорвется.
Теперь Медуза хочет узнать максимальное время в секундах до взрыва бомбы при оптимальном использовании инструментов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное время в секундах до взрыва бомбы.
Примечание
Пусть \(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\) секунд.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 3 3
1 1 7
7 1 5
1 2 5 6 8
|
9
21
|