题目描述

一排 N 个格子，编号 1 到 N。第 i 个格子上有分数 a[i]（可正可负）。

你从格子 1 出发，目标到达格子 N。每一步可以跳 1 格或 2 格，到达某个格子时获得该格子的分数。

特殊规则： 如果连续两次都跳 2 格，需要额外扣 B 分（作为体力惩罚）。

求到达格子 N 能获得的最大总分。起点和终点的分数都会计入。

输入格式

第一行两个整数 N, B 第二行 N 个整数 a[1], a[2], ..., a[N]

输出格式

一个整数：最大总分

6 3
3 5 -2 8 1 4

21

5 10
1 -1 1 -1 100

101

数据范围与提示

2 ≤ N ≤ 10000 1 ≤ B ≤ 1000 -1000 ≤ a[i] ≤ 1000