Stock exchange

Interview

Time limit1sMemory limit512 MB

Summary

Given daily prices and a fixed fee per buy, find the maximum total profit when holding at most one share at a time and each share must be sold later.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Array, Implementation
Solved: No attempts yet

Problem

A beginner investor wants to learn how to trade shares. With no experience to go on, he picked a single company and wrote down that company's closing share price on each of N consecutive days. Once he had the record, he wondered how much he could have made by trading over that period. He is wealthy enough to buy any number of shares, but he is careful, so he decided never to hold more than one share at any moment.

A broker always sits in the middle, so the brokerage charges a fixed fee of C for every share he buys.

On each day he does exactly one of three things: buy one share, sell the share he is holding, or nothing. A share he buys must be sold on a later day. The profit of a single trade is the selling price minus the buying price minus the fee C. Compute the largest total profit he could have made by trading on some of the N days. Trading on no day at all is allowed and gives a profit of 0.

Input

The first line contains two integers N and C ( $1 \le N \le 2 \times 10^5$ , $0 \le C \le 30$ ).

The second line contains the prices $P_1, P_2, \dots, P_N$ for days 1 through N, in order. Each price satisfies $1 \le P_i \le 1000$ .

Output

Print the maximum profit as a single integer on one line.

Examples3

Example 1
Input
```
6 10
100 120 130 80 50 40
```
Expected output
```
20
```
Example 2
Input
```
5 10
70 80 50 40 50
```
Expected output
```
0
```

Example 3

Input

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

Expected output