Это простая версия задачи. В этой версии задачи ответ нужно вычислить один раз. В этой версии задачи взломы запрещены.
В компьютерной игре вы сражаетесь против \(n\) монстров. Монстр с номером \(i\) имеет \(a_i\) единиц здоровья, где \(a_i\) — целое число. Монстр жив, пока имеет хотя бы \(1\) единицу здоровья.
Вы можете использовать заклинания двух типов:
- Нанести \(1\) единицу урона любому живому монстру на ваш выбор.
- Нанести \(1\) единицу урона всем живым монстрам. Если хотя бы один монстр умирает (оказывается с \(0\) единицами здоровья) в результате этого действия — повторить его (и продолжать повторять, пока хотя бы один монстр умирает после каждого применения).
При нанесении \(1\) единицы урона здоровье монстра уменьшается на \(1\).
Заклинания типа 1 могут быть использованы сколько угодно раз, а заклинание типа 2 — не более одного раза за игру.
Какое наименьшее число раз вам нужно применить заклинания типа 1, чтобы убить всех монстров?
Выходные данные
Для каждого набора входных данных выведите одно целое число — наименьшее число раз, которое нужно применить заклинания типа 1, чтобы убить всех монстров.
Примечание
В первом наборе входных данных начальные значения здоровья у монстров равны \([3, 1, 2]\). Достаточно применить заклинание типа 2:
- Здоровья монстров становятся равны \([2, 0, 1]\). Так как монстр номер \(2\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([1, 0, 0]\). Так как монстр номер \(3\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 0]\). Так как монстр номер \(1\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 0]\).
Так как можно обойтись вообще без заклинаний типа 1, ответ равен \(0\).
Во втором наборе входных данных начальные значения здоровья у монстров равны \([4, 1, 5, 4, 1, 1]\). Одной из оптимальных является следующая последовательность действий:
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(1\). Здоровья монстров становятся равны \([3, 1, 5, 4, 1, 1]\).
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(4\). Здоровья монстров становятся равны \([3, 1, 5, 3, 1, 1]\).
- Используя заклинание типа 1, снова нанести \(1\) единицу урона монстру номер \(4\). Здоровья монстров становятся равны \([3, 1, 5, 2, 1, 1]\).
- Использовать заклинание типа 2:
- Здоровья монстров становятся равны \([2, 0, 4, 1, 0, 0]\). Так как монстры номер \(2\), \(5\) и \(6\) умерли, заклинание повторяется.
- Здоровья монстров становятся равны \([1, 0, 3, 0, 0, 0]\). Так как монстр номер \(4\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 2, 0, 0, 0]\). Так как монстр номер \(1\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 1, 0, 0, 0]\).
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(3\). Здоровья монстров становятся равны \([0, 0, 0, 0, 0, 0]\).
Всего заклинания типа 1 были применены \(4\) раза. Можно показать, что это наименьшее возможное число.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
3 1 2
6
4 1 5 4 1 1
|
0
4
|