题目内容

你在玩地宫探宝游戏，地宫中每块地砖上都有不同价值的财宝，每回合你有三种走法：

1. 移动到下一块地砖
2. 跳过下一块地砖，移动到第二块地砖
3. 跳过下面的第一、第二块地砖，移动到第三块地砖

请在回合数耗尽前，携带最多的财宝逃离地宫。

设定：

1. 逃离失数：回合数耗尽仍未到达最后一块地砖（起点在地宫之外，目的地是最后一块地砖）
2. 自动拾取落脚地砖上的财宝
3. 地砖按照直线排列

输入描述

$n$（地砖个数，取值$[5,10000]$）$m$（回合数上限，取值[2,5000]）

$n$个整数（空格分割，表示每块地砖上财宝价值，取值$[0,5]$）

注意：所有的输入均为整数，用空格分割，题目保证输入合法，无需校验输入

输出描述

输出：携带的财宝总价（要求找到财宝总价最大值），如无法逃离则返回 $-1$

样例1

输入

5 3
1 2 1 1 3

输出

6

说明

第一行：有5块地砖，要求3步逃离 第二行：5个整数，分别表示地砖上的财宝价值

最优走法： 第一步：第二块地砖，拾取价值为2的财宝 第二步：第三块或第四块，拾取价值为1的财宝 第三步：第五块地砖，拾取价值为3的财宝

财宝价值共计：6

样例2

输入

10 3
0 0 3 1 2 3 0 0 0 0

输出

-1

说明

回合数是3，最大移动距离是9，无法在回合数耗尽前逃离