Мальчик Смайло играет в новую игру! В игре есть \(n\) орд монстров, в \(i\)-й орде \(a_i\) монстров. Цель игры — уничтожить всех монстров. Для этого у вас есть два типа атак и счетчик комбо \(x\), изначально равный \(0\):
- Первый тип атаки: вы выбираете число \(i\) от \(1\) до \(n\) такое, что в орде с номером \(i\) остался хотя бы один монстр. Затем вы убиваете одного монстра из орды с номером \(i\), и счетчик комбо \(x\) увеличивается на \(1\).
- Второй тип атаки: вы выбираете число \(i\) от \(1\) до \(n\) такое, что в орде с номером \(i\) осталось хотя бы \(x\) монстров. Затем вы применяете ультимейт и убиваете \(x\) монстров из орды под номером \(i\). После этого \(x\) обнуляется.
Ваша задача — зачистить всех монстров, то есть сделать так, чтобы ни в одной орде не осталось ни одного монстра. Смайло хочет как можно скорее победить, поэтому скажите, какое минимальное число атак можно применить?
Выходные данные
Для каждого набора входных данных выведите минимальное число атак, которое нужно, чтобы убить всех монстров.
Примечание
В первом наборе входных данных можно применить атаку первого типа по одному разу на \(1\)-ю, \(3\)-ю и \(4\)-ю орду, затем добить атакой второго типа \(2\)-ю орду. Итого нужно \(4\) атаки.
Во втором наборе входных данных можно применить атаку первого типа по одному разу на \(1\)-ю, \(3\)-ю орду, затем добить атакой второго типа \(2\)-ю орду, затем применить атаку первого типа один раз на \(4\)-ю орду. Итого нужно \(4\) атаки.
В четвёртом наборе входных данных можно применить атаку первого типа один раз на \(1\)-ю орду, два раза на \(2\)-ю орду, затем применить один раз атаку второго типа на \(2\)-ю орду, затем применить один раз атаку первого типа на \(2\)-ю орду. Итого нужно \(5\) атак.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6
|
4
4
11
5
|