cho.sh

Stock exchange

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.

Medium5Dynamic programmingGreedyArrayImplementationInterviewNo attempts yetTime limit1sMemory limit512 MB

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≤N≤2×1051 \le N \le 2 \times 10^5, 0≤C≤300 \le C \le 30).

The second line contains the prices P1,P2,…,PNP_1, P_2, \dots, P_N for days 1 through N, in order. Each price satisfies 1≤Pi≤10001 \le P_i \le 1000.

Output

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