Sane's Monthly Algorithms Challenge: November 2008

You have illegally obtained some insider information about the projected trend of a particular stock over the next $24$ hours. With this information, you plan to repeatedly buy and sell the stock according to what will rake in the most profit.

The information consists of $n$ values, each being the value of the stock at each time interval over a period of $24$ hours. To buy one share of the stock, you must pay the value predicted for the current interval. To sell one share of the stock, you will receive the value predicted for that interval.

In the first Stock Market Challenge (July's SMAC Challenge), you were attempting to avoid rousing suspicion with your $1000$ shares by only making one transaction. But this time you will be greedy: You may buy and sell the $1000$ shares an unlimited number of times throughout the day (as long as you do not have more than $1000$ in your holding at any one moment).

However, you will also need to pay a fixed commission rate to your broker on each transaction (every buy and every sell).

Using the stock's projection, determine the optimum times to buy then sell, and the resulting maximum profit. It is always guaranteed that a profit can be made.

Input Specification

On the first line is the integer $n$ $(2\le n\le 1000000)$, and the fixed integer amount of commission per transaction.

On the next $n$ lines are the prices for the $i$-th time intervals $(1\le i\le n)$. Each line contains a floating point number with no more than $2$ decimal places, representing the share's price for the $i$-th time interval.

Output Specification

Output the maximum possible integer profit made in dollars, respectively.

Grading

For $10$ of the $15$ test files, there will be no commission.

Sample Input

24 30
1.00
1.05
1.06
1.07
1.03
0.98
0.99
1.01
1.09
1.14
1.13
1.12
1.11
1.10
1.09
1.08
1.07
1.06
1.05
1.04
1.03
1.02
1.01
1.00

Sample Output

110

Explanation of Sample Output

1)  Buy  1000 at 1.00 for - 1000 - 30 = - $1030
4)  Sell 1000 at 1.07 for + 1070 - 30 = + $1040
6)  Buy  1000 at 0.98 for - 980  - 30 = - $1010
10) Sell 1000 at 1.14 for + 1140 - 30 = + $1110
                                        -------
                                           $110