该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

你每天会收到一些 euro，可能正也可能负，银行允许你在某天将手头所有的 euro 兑 换成 lei。第 i 天的兑换比率是 1 euro ：i lei，同时你必须再多付出 T lei 被银行收 取。

在 N 天你必须兑换所有持有的 euro。

你的任务是寻找一个兑换方案，使得第 N 天结束时能得到最多的 lei。

Format

Input

第一行两个整数 N 和 T。接下来一行 N 个整数 Ci，表示第 i 天开始时得到 Ci 的euro。

Output

仅一行，表示能得到的最多的 lei。

Samples

7 1
-10 3 -2 4 -6 2 3

17

Samples Description

在第 1,5,7 天兑换，(-10)*1-1+(3+(-2)+4+(-6))*5-1+(2+3)*7-1=17。

Limitation

对于 20%的数据，1<=N<=15；对于 100%的数据，

1<=N<=1000,1<=T<=1000,|Ci|<=1000；