ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1431. Сертификаты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Знаете ли вы, что некоторые студенты, вместо того, чтобы учиться, участвуют в разных соревнованиях? Иногда такие студенты даже получают дипломы за победы в этих соревнованиях. А знаете ли вы, что некоторые деканы собирают и развешивают на стене деканата цветные копии студенческих дипломов? Вы не поверите, но когда дипломов накапливается много, иногда в деканате ставят дополнительные стенки! Но прежде чем поставить очередную стенку, надо определить ее размер. А для этого нужен проект размещения дипломов на стене. Поэтому нанимают дизайнера — чтобы все было красиво.
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду. И не как попало, а симметрично относительно центра стены. И чтобы больше в этом ряду ничего не висело. Но секретарь резонно заметила, что типов дипломов много, и в таком случае высоты стены может просто не хватить. Тогда дизайнер согласился, что вперемешку с дипломами одного типа можно повесить дипломы другого типа. Но в одном ряду уж точно не должно быть больше двух типов дипломов. И обязательно надо чтобы было строгое чередование этих двух типов внутри ряда. И чтоб сохранялась симметрия относительно центра.
Никому не охота ломать голову, что же все эти требования означают, поэтому декан и поручил развешивание самим студентам. Пока строители не ушли, вам нужно найти минимально возможное количество рядов, в которые можно разместить все дипломы, не нарушая требований дизайнера. В случае чего, придется поставить еще несколько стенок. Можно считать, что в ширину стены деканата бесконечны.

Исходные данные

В первой строке находится число N (1 ≤ N ≤ 18) — количество разных типов дипломов. Во второй строке через пробел выписаны количества дипломов каждого типа, N чисел не меньших 1 и не превосходящих 30.

Результат

Вывести минимальное количество рядов, в которые можно разместить все дипломы в соответствии с требованиями дизайнера.

Пример

исходные данныерезультат
6
8 15 13 8 14 8
5
Автор задачи: Станислав Васильев
Источник задачи: Седьмое открытое личное первенство УрГУ по спортивному программированию - 25 февраля 2006 года