Монокарп играет в компьютерную игру. Он должен уничтожить \(n\) монстров, у \(i\)-го из них \(h_i\) здоровья.
У Монокарпа есть два заклинания, каждое из которых он может применить произвольное количество раз (возможно, ноль) и в произвольном порядке:
- выбрать ровно двух живых монстров и уменьшить их здоровье на \(1\);
- выбрать ровно одного живого монстра и убить его.
Когда здоровье монстра становится равным \(0\), он умирает.
Какое наименьшее количество раз Монокарп должен применить заклинания, чтобы убить всех монстров?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее количество раз, которое Монокарп должен применить заклинания, чтобы убить всех монстров.
Примечание
В первом наборе входных данных изначальный список здоровья \([1, 2, 1, 2]\). Применяются три заклинания:
- первое заклинание на монстров \(1\) и \(2\) — монстр \(1\) умирает, у монстр \(2\) здоровье становится \(1\), новый список здоровья \([0, 1, 1, 2]\);
- первое заклинание на монстров \(3\) и \(4\) — монстр \(3\) умирает, у монстр \(4\) здоровье становится \(1\), новый список здоровья \([0, 1, 0, 1]\);
- первое заклинание на монстров \(2\) и \(4\) — оба монстра \(2\) и \(4\) умирают.
Во втором наборе входных данных изначальный список здоровья \([2, 4, 2]\). Применяются три заклинания:
- первое заклинание на монстров \(1\) и \(3\) — у обоих монстров здоровье становится \(1\), новый список здоровья \([1, 4, 1]\);
- второе заклинание на монстра \(2\) — монстр \(2\) умирает, новый список здоровья \([1, 0, 1]\);
- первое заклинание на монстров \(1\) и \(3\) — оба монстра \(1\) и \(3\) умирают.
В третьем наборе изначальный список здоровья \([1, 2, 3, 4, 5]\). Применяются пять заклинаний. \(i\)-е из них убивает \(i\)-го монстра вторым заклинанием. Последовательность списков здоровья: \([1, 2, 3, 4, 5]\) \(\rightarrow\) \([0, 2, 3, 4, 5]\) \(\rightarrow\) \([0, 0, 3, 4, 5]\) \(\rightarrow\) \([0, 0, 0, 4, 5]\) \(\rightarrow\) \([0, 0, 0, 0, 5]\) \(\rightarrow\) \([0, 0, 0, 0, 0]\).