这个游戏是这样的，wind先写下一排数。既然是一排，当然有首尾咯。
wind和小杉每次只能从这排数的头或尾取一个数。
最后谁取的数的和多，谁就赢了。
假如你是小杉，请算出你最多能取到的和。
wind的智商是很高的（怪不得小杉一直输），你必须知道他总是做出最优决策。

每组测试数据的 第一行仅有一个数n(n< =2000) 第二行也仅有一个数，0表示wind先取数，1表示小杉先取数 第三行有n个数，是wind给出的一排数。这n个数均不超过1e6

对每组测试数据输出一行 仅有一个整数s 表示小杉最多能取到多少数

如果您AC此题
那么...................................................................您就AC了此题

UVAOJ lolanv改编