Квитки в кіно
У цій задачі вам пропонується допомогти касиру, який продає квитки в кіно. Залишилось два вільних ряди, один за другим, по m місць у кожному. Місця у кожному ряді нумеруютсья зліва направо числами від 1 до m. У черзі стоять люди групами по a[i] чоловік. Кожну групу можна посадити у один з рядів підряд, або, якщо a[i] парне, можна посадити її у два ряди на місця з однаковими номерами.
Касир у роздумах: чи вдасться йому посадити усі групи, дотримуючись цих вимог? Допоможіть йому, знайшовши мінімальну довжину ряда m, при якій можна посадити усі групи, дотримуючись вимог.
Вхідні дані
У першому рядку знаходиться кількість груп n (1 ≤ n ≤ 1000). У другому рядку задані n натуральних чисел a[1], a[2], ..., a[n], тут a[i] - кількість людей в i-й групі. Сума усіх a[i] не перевищує 10^5.
Вихідні дані
Виведіть одне ціле число - мінімальну довжину одного ряду, при якій получиться посадити усі n груп.