题目内容

小明正在挑战一款地宫探宝游戏。地宫中的地砖沿一条直线排列，每块地砖上均放置着价值不同的财宝。

游戏进行过程中，每个回合小明只能选择以下三种移动方式之一：

1. 向前移动到下一块地砖；
2. 越过下一块地砖，直接移动到第二块地砖；
3. 连续跳过前方的第一、第二块地砖，移动到第三块地砖。

地宫即将坍塌，所以需要在指定回合数以内之前离开地宫，并尽可能携带更多财宝。

游戏规则如下：

• 起点位于地宫之外，最终目标位置为地宫中的最后一块地砖。
• 每次移动后，角色会自动获得当前落脚地砖上的财宝。
• 如果在回合数耗尽时仍未成功到达最后一块地砖，则判定为逃离失败。

约束条件

• 地砖数量 $n$ 的范围为 5 到 10000。
• 回合数上限 $m$ 的范围为 2 到 5000。
• 每块地砖上的财宝价值为从 0 到 5 的整数。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示地砖数量和回合数上限。

第二行包含 $n$ 个整数，按地砖编号 $1$ 到 $n$ 的顺序给出每块地砖上的财宝价值，整数之间用空格分隔。

输出描述

输出一个整数，表示在成功逃离地宫的情况下可以获得的财宝总价值最大值；如果无法逃离，输出 -1。

样例1

输入

5 2
1 2 3 4 5

输出

8

说明

共有 5 块地砖，最多 2 个回合。从 0 到 5 的总前进距离为 5。

两回合每回合可走 1、2 或 3 格，能凑成 5 的组合只有 $2+3$ 和 $3+2$。

若第一回合走 2 格到位置 2，第二回合走 3 格到位置 5，拾取价值为 $2+5=7$。

若第一回合走 3 格到位置 3，第二回合走 2 格到位置 5，拾取价值为 $3+5=8$。

因此最大总价值为 8。

样例2

输入

10 3
1 2 3 4 5 4 3 2 1 0

输出

-1

说明

共有 10 块地砖，最多 3 个回合。每回合最多前进 3 格，所以 3 个回合最多前进 $3\times3=9$ 格。

由于 9 小于目标位置 10，即使每回合都走最大步长也无法到达位置 10，因此无法逃离，输出 -1。

样例3

输入

6 4
0 5 5 0 0 1

输出

11

说明

共有 6 块地砖，最多 4 个回合。需要从 0 到达 6。

一种可行落脚序列为 $0\to1\to2\to3\to6$，步长依次为 $1,1,1,3$，拾取地砖编号为 1、2、3、6，价值和为 $0+5+5+1=11$。

在所有可行路径中，这是能够取得的最大值，因此输出 11。

样例4

输入

5 10
1 1 1 1 5

输出

9

说明

共有 5 块地砖，最多 10 个回合。由于回合数足够多，可以每回合只前进 1 格，依次经过位置 1、2、3、4、5。

这样能够拾取所有地砖，总价值为 $1+1+1+1+5=9$，因此输出 9。