На столе стоят n коробок с разноцветными шарами. Цвета пронумерованы от 1 до n. В i-й коробке лежит ai шаров i-го цвета. Требуется разбить шары на минимальное количество наборов таких, что:
- каждый шар принадлежит ровно одному набору,
- каждому набору принадлежит хотя бы один шар,
- в каждом наборе все шары одного цвета,
- размеры любых двух наборов отличаются не более чем на 1.
Выведите искомое минимальное количество наборов.
Выходные данные
Выведите одно число — минимальное возможное количество наборов.
Примечание
В первом примере можно разбить шары на следующие наборы: первую коробку — на набор из 4 шаров, вторую — на наборы из 3 и 4 шаров и третью — на два набора из 4 шаров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 7 8
|
5
|
|
2
|
2
2 7
|
4
|