题目背景

Pixiv:みこフライ

等我严肃地 AC 了这题，就严肃地去喝下午茶。

题目描述

在某个悠闲的下午，Furai 面前摆着 $n$ 块精致的小点心，排成一列。第 $i$ 块点心的“甜蜜值”为 $a_i$（可能是负数，意味着不太好吃）。

Furai 可以任选一些点心来组合（也可以一个都不选）。把选中的点心下标按从小到大排序后，显然会形成若干段连续的区间组合。 例如：选中点心的下标 $2,3,4,7,8$，会形成两段区间组合：$[2,4]$ 和 $[7,8]$；选中点心的下标 $5,6,7$，就是一段区间组合 $[5,7]$；如果一个都不选，则没有区间组合。

对于每一个区间组合 $[L,R]$ 中，Furai 会重新按顺序给每个点心一个编号，也就是 $1,2,...,R-L+1$，她只打算认真品尝编号为奇数的点心（获得对应的“甜蜜值”），而编号为偶数的点心只是为了让组合看起来更丰富，实际上她并不吃它们（因此不计“甜蜜值”）。

每次开始品尝一个新的组合，Furai 都需要花费 $C$ 的“甜蜜值”来调整心情。

这次下午茶时光的总“甜蜜值”是所有区间组合的“甜蜜值”之和。

虽然 Furai 肯定吃不完这么多点心，但是她还是希望知道能得到的最大“甜蜜值”。

输入格式

第一行两个正整数 $n,C\ (1\le n\le3\times10^5,1\le C\le10^9)$，表示点心数量和每次开始品尝新组合的花费。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i\ (-10^9\le a_i\le10^9)$，表示第 $i$ 个点心的“甜蜜值”。

输出格式

输出一个整数，表示 Furai 能得到的最大总“甜蜜值”。

4 2
7 4 5 11

14

5 3
3 -4 -2 0 4

2

提示

对于第一组样例，Furai 需要选择 $a_1,a_4$，也就是区间组合 $[1,1],[4,4]$ 来获得最大总“甜蜜值”：$7-2+11-2=14$。

对于第二组样例，她需要选择 $a_1,a_2,a_3,a_4,a_5$，也就是区间组合 $[1,5]$，这次她不得不吃掉一个不太好吃的点心 $a_3$，才能获得最大总“甜蜜值”：$3+(-2)+4-3=2$。可以证明没有更大的总“甜蜜值”。