Несправедливий поділ
Альберт та його дві сестри Бетті та Карина ділять майно. Вартості речей, що дістались у спадок, виписані на аркуші паперу. Альберт бере ножиці і розрізає папір між деякими двома числами. Потім Бетті таким же чином розрізає один зі шматків. Далі Карина вибирає шматок з максимальною сумою. З двох шматків, що залишились, вибір робить Бетті. Останній шматок дістається Альберту.
Кожен з учасників при виборі намагається отримати максимальну суму спадку. Сестри злі на брата, і у своїх виборах будуть наказувати його, якщо лише при цьому не постраждає їх прибуток. Наприклад, якщо у однієї із сестер є два різніе варіанти отримати одну і ту ж суму майна, то вона обере той з варіантів, при якому її сестра отримає більше.
Знайти максимальну суму, яку може забезпечити собі Альберт своїм першим розрізом.
Вхідні дані
Перший рядок містить кількість речей n (n ≤ 50), які потрібно поділити. У другому рядку записано n цілих чисел - їх вартості. Вартість кожної речі лежить у межах від 1 до 1000.
Вихідні дані
Вивести максимальну суму, яку може забезпечити собі Альберт своїм першим розрізом.