Альберт и его две сестры Бетти и Карина делят имущество. Стоимости вещей, доставшихся в наследство, выписаны на куске бумаги. Альберт берет ножницы и разрезает бумагу между некоторыми двумя числами. Потом Бетти таким же образом разрезает один из кусков. Далее Карина выбирает кусок с максимальной суммой. Из оставшихся двух кусков выбор делает Бетти. Последний кусок достается Альберту.

Каждый из участников при выборе старается получить максимальную сумму наследства. Сестры обижены на брата, и в своих выборах будут наказывать его, если только при этом не пострадает их прибыль. Например, если у одной из сестер есть два разные варианта получить одну и туже сумму имущества, то она выберет тот из вариантов, при котором ее сестра получит больше.

Найти максимальную сумму, которую может обеспечить себе Альберт своим первым разрезом.

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

Первая строка содержит количество вещей n (n ≤ 50), подлежащих дележу. Во второй строке записаны n целых чисел - их стоимости. Стоимость каждой вещи лежит в пределах от 1 до 1000.

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

Вывести максимальную сумму, которую может обеспечить себе Альберт своим первым разрезом.