В этой задаче Вам предлагается помочь кассиру, продающему билеты в кино. Осталось два свободных ряда, один за другим, по m мест в каждом. Места в каждом ряду нумеруются слева направо числами от 1 до m. В очереди стоят люди группами по ai человек. Каждую группу можно посадить в один из рядов подряд, либо, если ai чётное, можно посадить её в два ряда на места с одинаковыми номерами.

Кассир в раздумьи: удастся ли ему посадить все группы, соблюдая эти требования? Помогите ему, найдя минимальную длину ряда m, при которой можно посадить все группы, соблюдая их.

Входные данные

В первой строке находится количество групп n (1 ≤ n ≤ 1000). Во второй строке заданы n натуральных чисел a1, a2, ..., an, здесь ai - количество людей в i-й группе. Сумма всех ai не превосходит 105.

Выходные данные

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