题目描述
33DAI 和 Kitten 正在玩一款游戏。游戏中有 个城市(),从左到右编号从 ,编号为 的城市有 的资源。
Kitten 可以任选一个城市开始实行声东击西战略,假设她选择城市 。那么 33DAI 就会警觉并前往城市 。这需要花费 33DAI 分钟的时间。33DAI 到达后就会封锁城市 使得不能从 走到 ,也不能从 走到 。如果此时 Kitten 就在城市 ,那么 Kitten 就会直接输掉游戏。
Kitten 每分钟可以选择待在原地或者走到左边或者右边的城市(即从城市 走到城市 或 )。
请你帮 Kitten 决定起始城市及每分钟的移动策略,来不输掉游戏,并最大化她到过的城市资源之和。
输入
第一行为一个数 。
第二行为 个整数 。
输出
一个整数,即她到过的城市资源之和的最大值。
样例输入 复制
2
-5 2
样例输出 复制
-3
提示
数据规模与约定
对于 的数据,,。
- 子任务 1(10 分):保证 。
- 子任务 2(20 分):保证 。
- 子任务 3(30 分):保证 。
- 子任务 4(40 分):没有特殊限制。