Problem A
Short Sell
Simone is learning to trade crypto currencies. Right now, she is looking into a new currency called CryptoKattis. A CryptoKattis can be used to improve your Kattis ranklist score without having to solve problems.
Simone, unlike most competitive programmers, is very perceptive of competition trends. She has lately noticed many coders talking about a new online judge called Doggo, and suspect that using the Kattis judge will soon fall out of fashion. This, of course, will cause the CryptoKattis to rapidly fall in value once demand fades.
To take advantage of this, Simone has performed very careful market research. This has allowed her to estimate the price of a CryptoKattis in dollars during the next $N$ days. She intends to use this data to perform a short sell. This means she will at some day borrow $100$ CryptoKattis from a bank, immediately selling the currency. At some other day, she must purchase the same amount of CryptoKattis to repay her loan. For every day between (and including) these two days, she must pay $K$ dollars in interest. What is the maximum profit Simone can make by carefully choosing when to borrow and repay the $100$ CryptoKattis?
Input
The first line of the input contains two integers $1 \le N \le 100\, 000$ and $1 \le K \le 100$. $N$ is the number of days you know the CryptoKattis price of, and $K$ is the cost in dollars of borrowing CryptoKattis per day.
The next line contains $N$ integers separated by spaces. These are the CryptoKattis prices during the $N$ days. Each CryptoKattis price is between $1$ and $100\, 000$ dollars.
Output
Output a single decimal number; the maximum profit you can make performing a short sell. If you cannot make a profit no matter what short sell you make, output $0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 10 1000 980 960 940 10 |
98950 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 100 100 100 100 103 100 |
100 |
