#78. 「2023 新生杯」破釜橙舟

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: woruo

题目描述

猫猫冒险队闯入了 Koishi 的城堡,却遭遇了危机。

战士橙子被 只怪物围攻,他们排成一行,橙子在第 个位置(从左往右数)。

橙子和每只怪物都有一个战斗力 ,他只能打败战斗力不超过他的怪物,且橙子每次可以选择攻击他左边或右边的一只怪物。

如果橙子杀死了一只怪物,那么这只怪物的位置就会被它的相邻的怪物填补。

Koishi 对橙子施放了诅咒,影响了他的战斗力:

  • 如果橙子打败了他左边的一只战力为 的怪物(第 到第 个位置),那么橙子的战斗力就会变成
  • 如果橙子打败了他右边的一只战力为 的怪物(第 到第 个位置),那么橙子的战斗力就会增加

橙子想要找出一种攻击顺序,在能打败所有怪物的情况下最后保留的战斗力尽可能大。

输入格式

第一行一两个正整数 ,用一个空格分隔,代表橙子和怪物的数量总和为 ,橙子在从左至右的第 位。

第二行 个整数 ,用一个空格分隔,代表从左至右数的第 个生物的战斗力为

输出格式

输出一行一个正整数 ,代表橙子最终能达到的最大攻击力。

若橙子无法战胜所有怪物,则输出

样例

样例输入 1

5 3
5 6 5 3 4

样例输出 1

9

样例输入 2

5 3
5 10 5 3 4

样例输出 2

5