URI Online Judge | 1932

Stock Market

By Vinícius Fernandes dos Santos, Bruno J. Adami, Cláudio L. Lucchesi Brazil

Timelimit: 1

A beginner investor wants to learn how to invest in the stock market. As he does not have any experience, he selected one company and followed daily the value of the stock during N days. At the end, he wondered how much money he would have won if he had invested during the time he followed the stock value. To be honest, the investor is multi billionaire and has a lot of money, enough to buy any amount of stock actions of the company. However, as he is very careful with his investments, he decided that he would never have more than one stock of the company.

To cover his costs, the stockbroker charges a fixed rate of C dollars for every stock purchase.

You have to calculate the maximum profit that the investor could have won investing during the N days, having also the option of not to invest any money.


The input consists of several test cases. The first line of a test case contains two integers, N and C (1 ≤ N ≤ 2 × 105, 0 ≤ C ≤ 30). The second line contains the N prices P1, P2, …, PN of the days 1, 2,…, N, respectively. Every price Pi satisfies 1 ≤ Pi ≤ 1000.


For each test case in the input your program must produce exactly one line, containing exactly one integer, the maximum profit of the investor, in dollars.
Input Example Output Example

6 10

100 120 130 80 50 40


5 10

70 80 50 40 50


13 30

10 80 20 40 30 50 40 60 50 70 60 10 200