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

题目描述

你每天会收到一些euro，可能正也可能负，银行允许你在某天将手头所有的euro兑换成lei。

第i 天的兑换比率是$\red 1$ euro ：$\red i$ lei，同时你必须再多付出$\red {T}$ lei被银行收取。

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

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

输入格式

第一行两个整数$\red N$和$\red T$。

接下来一行$\red N$个整数$\red {C_i}$，表示第i天开始时得到$\red {C_i}$的euro。

输出格式

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

样例

输入样例

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

输出样例

17

提示

对于$\red {20\%}$的数据，$\red {1<=N<=15}$；

对于$\red {100\%}$的数据，$\red {1<=N<=1000,1<=T<=1000,|Ci|<=1000}$；

样例解释

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