题目描述
你每天会收到一些euro
,可能正也可能负,银行允许你在某天将手头所有的euro
兑换成lei
。
第i 天的兑换比率是1 euro
:i lei
,同时你必须再多付出T lei
被银行收取。
在N 天你必须兑换所有持有的euro
。
你的任务是寻找一个兑换方案,使得第N天结束时能得到最多的lei
。
输入格式
第一行两个整数N和T。
接下来一行N个整数Ci,表示第i天开始时得到Ci的euro
。
输出格式
仅一行,表示能得到的最多的lei
。
样例
输入样例
7 1
-10 3 -2 4 -6 2 3
输出样例
17
提示
对于20%的数据,1<=N<=15;
对于100%的数据,1<=N<=1000,1<=T<=1000,∣Ci∣<=1000;
样例解释
在第1,5,7天兑换,(−10)∗1−1+(3+(−2)+4+(−6))∗5−1+(2+3)∗7−1=17。