定义一个序列的权值和为这个序列中元素的总和。现在给你一个序列 a ，请从中选出一个子序列 b，使得该子序列总价值最大。
但这个求解问题太简单了，我们决定添加两个条件：
1：定义江莉值为：选出的子序列中相邻两个元素在原数组中的下标之差的总和。例如原数组为 a={10,9,8,7,6}，选出 b={10,8,6} ，得到的江莉值为：(3-1)+(5-3)=4。
2：定义惩罚值为：在选出的子序列中，如果两相邻元素 b_i, b_i+1 满足 b_i > b_i+1，则惩罚值+t。
给你一个长度为 n 的序列 a，请从中选出一个子序列 b，并最大化 b 的权值和+江莉值-惩罚值。
注：子序列是指在原序列中选出部分数，以其在原序列中的顺序所排成的新序列，选出的数不一定在原序列中连续。

第一行输入一个正整数 n (1<= n <= 2*10⁵)，代表给定序列的长度。
第二行输入一个正整数 t (1<= t <= 2*10⁵)，代表满足一定条件后惩罚值添加的值。
第三行输入 n 个正整数 a_i (-200 <= a_i <= 200)，代表给定序列中的元素。

输出一行一个整数，代表选出的最大的 b 的权值和+江莉值-惩罚值。

样例2

输入

9
2
6 7 8 9 10 -1 -1 -1 -1

输出

45

提示

样例1中，选择了整个数组。
样例2中，选择6, 7, 8, 9, 10及最后一个-1。

郑州轻工业大学2023级新生程序设计大赛暨省内高校邀请赛