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