You have just opened a new bank account, where you will receive amounts in euro currency. When you opened the account, you had no euros in it and no lei in your possession (lei is the currency used in Romania). During each of the next N days, you will receive various amounts of euros; the amounts may be negative, in which case the total amount of euros in your account will decrease. It is possible for you to have a negative balance of euros in your account at times. At the end of each day, the bank allows you to convert the whole amount of euro in your account into lei. The daily exchange rate varies according to the following rule: during the Kth day, a euro can be exchanged for K lei. The bank also charges you T lei for each conversion. Therefore, if at the end of day K you have S euros in your account, and you decide to convert them, you will receive S*K-T lei (of course, S can be negative). At the end of day N, you must convert your remaining euros into lei, even if the amount is non-positive.

Task

Your objective is to maximize the final amount of lei you have at the end of the N-day period.

Input

The first line of the input file euro.in contains two integers, N and T, separated by blanks. The next line contains N integers, specifying the amount of euros you will receive at the beginning of each day.

Output

Constraints

• 1 <= N <= 34 567
• 0 <= T <= 34 567
• 80% of the test cases will have T <= 255
• The amount of euros you will receive each day is an integer from the interval [-1000,1000]
• You are only allowed to convert euros into lei, and not lei into euros.
• For the result, it is recommended that you use the data types int64 or extended in Pascal and long long or double in C/C++ (depending on whether you want to use integer or floating point computations). It is guaranteed that the result fits into these data types, but it may exceed the bounds of smaller ones.

Sample Input

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

Sample Output

17

Explanation

At the end of the first day, you exchange the -10 euros you have received for -11=-10*1-1 lei. The second conversion takes place at the end of the 5th day, when you have -1 euros in your account (3-2+4-6). The amount of lei you gain is -6=(3-2+4-6)*5-1. You make the last conversion at the end of the 7th day, using the last 5 euros in your account (2+3). The amount of lei you gain is 34=(2+3)*7-1. The final amount of lei is 17=-11-6+34.

Time Limit: 0.4 seconds/test SubmitStatistics