eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Несправедливий поділ

Несправедливий поділ

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Альберт та його дві сестри Бетті та Карина ділять майно. Вартості речей, що дістались у спадок, виписані на аркуші паперу. Альберт бере ножиці і розрізає папір між деякими двома числами. Потім Бетті таким же чином розрізає один зі шматків. Далі Карина вибирає шматок з максимальною сумою. З двох шматків, що залишились, вибір робить Бетті. Останній шматок дістається Альберту.

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

Знайти максимальну суму, яку може забезпечити собі Альберт своїм першим розрізом.

Вхідні дані

Перший рядок містить кількість речей n (n50), які потрібно поділити. У другому рядку записано n цілих чисел - їх вартості. Вартість кожної речі лежить у межах від 1 до 1000.

Вихідні дані

Вивести максимальну суму, яку може забезпечити собі Альберт своїм першим розрізом.

Приклад

Вхідні дані #1
4
50 90 10 100
Вихідні дані #1
50