Билеты в кино
Билеты в кино
В этой задаче Вам предлагается помочь кассиру, продающему билеты в кино. Осталось два свободных ряда, один за другим, по m мест в каждом. Места в каждом ряду нумеруются слева направо числами от 1 до m. В очереди стоят люди группами по ai
человек. Каждую группу можно посадить в один из рядов подряд, либо, если ai
чётное, можно посадить её в два ряда на места с одинаковыми номерами.
Кассир в раздумьи: удастся ли ему посадить все группы, соблюдая эти требования? Помогите ему, найдя минимальную длину ряда m, при которой можно посадить все группы, соблюдая их.
Входные данные
В первой строке находится количество групп n (1 ≤ n ≤ 1000). Во второй строке заданы n натуральных чисел a1
, a2
, ..., an
, здесь ai
- количество людей в i-й группе. Сумма всех ai
не превосходит 105
.
Выходные данные
Выведите одно целое число - минимальную длину одного ряда, при которой получится посадить все n групп.
4 1 2 3 4
5
3 12 5 3
11