#1438. 欧元

欧元

题目描述

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

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

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

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

输入格式

第一行两个整数N\red NT\red T

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

输出格式

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

样例

输入样例

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

输出样例

17

提示

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

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

样例解释

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

统计

相关

在下列比赛中:

初中组测试

在以下作业中:

动态规划作业1