A36458.加固

时间限制：1000ms，内存限制：128MB

在一片森林里，住着 $n$ 只小猪。森林中还有一只大灰狼，它准备发动攻击，摧毁这些小猪的家园。

森林里的 $n$ 个小猪的家是一个环形，小猪们编号从 $1$ 到 $n$，也就是说第 $i$ 个小猪的邻居是第 $i - 1$ 只小猪和第 $i + 1$ 只小猪，

特别地，第 $1$ 只小猪的邻居是第 $n$ 只小猪和第 $2$ 只小猪。每只小猪 $i$ 的家里一开始都有 $a_i$ 个金币。大灰狼即将来袭，小猪们只能通过强化它们的家园来抵御攻击。

强化一只小猪的家园会从其每个邻居的家园里每次拿走 $c$ 个金币，来为自己的家园建设更好的防御措施。然而，强化操作并不会改变这只小猪的金币数量，只有它的邻居们的金币数量会减少。一只小猪家里的金币可能会变为负数。

当大灰狼攻击之后，所有进行过强化的小猪的家园将能够存活，而未进行强化的小猪家园将被摧毁，所有存活的家园继承原来的金币数量(包括负值），所有被摧毁的家园金币归零。

现在问题来了，经过强化安排后，小猪们在幸存的家园里能保留的金币总数最大值是多少？

输入共两行：
第一行包含两个整数 $n$ 和 $c$，表示小猪的数量和从每个邻居家园拿走的金币数量；
第二行包含 $n$ 个整数 $a_1,a_2,a\dots,a_n$ 表示每只小猪一开始拥有的金币数量。

对于每个测试用例，输出一个整数，表示大灰狼攻击后，经过强化方案后幸存的家园里能够保留的最大金币总数。

【数据范围】

对于 $100\%$ 的数据，$1\le c\le10^9,-10^9\le a_i \le 10^9$

测试点编号	数据范围
$1$	$3\le n\le10$
$2$	$n = 1$
$3$	$3\le n\le20$
$4$~$6$	$3\le n\le3000$
$7$~$10$	$3\le n\le2\times10^5$

$\color{red}\mathbf{Attention:}$

备注：由于 ACGO 竞赛测评机的数据点顺序与结果返回顺序不一致，如果你的程序在第三个测试点出错，请对 $n=1$ 的情况进行特判并输出 $0$。这表示没有邻居的小猪无法自我强化，因此会直接被摧毁。题目数据本身无误。

【样例解释】

样例组 #1：加固小猪 $2$ 的房子，所有小猪剩下的金币为 $[1,3,0]$。
样例组 #2：加固所有小猪的房子，所有小猪剩下的金币为 $[2,4,2]$。