Билеты в кино
В этой задаче Вам предлагается помочь кассиру, продающему билеты в кино. Осталось два свободных ряда, один за другим, по 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 групп.