Спустя 2 месяца после олимпиады друзья получили письмо от организаторов ВКОШП с предложением составить задачи на следующий год! С тех пор молодые шаманы регулярно обмениваются своими задачами.

Саша предложил Егору следующую задачу: «В один ряд выложены N карточек, на каждой из которых написано целое положительное число. Кирилл и Семён начинают по очереди забирать карточки. Разрешается брать только первую или последнюю карточку ряда. Кирилл берет первым. Число, записанное на карточке, добавляется к очкам игрока. Кирилл в последнее время очень занят, потому что он недавно устроился работать программистом в компанию, занимающуюся прокладкой туннелей в Европе. Поэтому ему некогда продумывать стратегию предстоящей игры и он просит Вас определить максимальную сумму, которую он может получить, при условии, что Семён играет оптимально.»

Егор быстро решил эту задачу, а Вы справитесь?