eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Квитки в кіно

Квитки в кіно

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У цій задачі вам пропонується допомогти касиру, який продає квитки в кіно. Залишилось два вільних ряди, один за другим, по m місць у кожному. Місця у кожному ряді нумеруютсья зліва направо числами від 1 до m. У черзі стоять люди групами по a[i] чоловік. Кожну групу можна посадити у один з рядів підряд, або, якщо a[i] парне, можна посадити її у два ряди на місця з однаковими номерами.

Касир у роздумах: чи вдасться йому посадити усі групи, дотримуючись цих вимог? Допоможіть йому, знайшовши мінімальну довжину ряда m, при якій можна посадити усі групи, дотримуючись вимог.

Вхідні дані

У першому рядку знаходиться кількість груп n (1n1000). У другому рядку задані n натуральних чисел a[1], a[2], ..., a[n], тут a[i] - кількість людей в i-й групі. Сума усіх a[i] не перевищує 10^5.

Вихідні дані

Виведіть одне ціле число - мінімальну довжину одного ряду, при якій получиться посадити усі n груп.

Приклад

Вхідні дані #1
4
1 2 3 4
Вихідні дані #1
5
Вхідні дані #2
3
12 5 3
Вихідні дані #2
11
Автор П.Мітрічев, І.Казменко