Дача
(Время: 1 сек. Память: 32 Мб Сложность: 19%)
Пришла весна. А это значит, что скоро придет лето и Тане пора готовиться к дачному сезону. У неё уже есть в наличии семена необходимых овощей и растений для ёё огорода. Однако, для того, чтобы вырастить растения, их сначала нужно посадить, а сделать это можно не раньше наступления определенного дня.
Всего у Тани N растений, i-му из которых требуется Ai дней для роста и созревания. Из-за сильной загруженности Таня не сможет сажать более одного растения в день, поэтому для неё сильно важен порядок, в котором она будет сажать растения.
Разумеется, она хочет, чтобы все растения созрели как можно раньше, чтобы как можно раньше их можно было начать использовать в приготовлении блюд.
Помогите Тане – найдите минимальное количество дней, через которое все растения смогут созреть при определенном порядке их высаживания.
Входные данные
В первой строке входного файла INPUT.TXT содержится число N – количество растений, которое есть у Тани (1 ≤ N ≤ 105).
Во второй строке содержится N целых чисел Ai, которые означают количество дней, требуемое для роста и созревания i-го растения (1 ≤ Ai ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество дней, через которое все растения могут вырасти и созреть при определенном порядке высаживания.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1 5 3 5 4 | 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
