The Central Sterile Services department processes surgical instruments in the order they arrive from the wards. Instruments cannot be reordered, but consecutive instruments may be grouped together. There are ~n~ instruments in the queue, and instrument ~i~ has calibration size ~a_i~.

The steriliser processes the instruments in contiguous batches. Each batch incurs a fixed setup cost ~S~. It also incurs a calibration cost: if the largest calibration size in a batch is ~M~, an instrument of size ~a_i~ contributes ~M-a_i~ to the calibration cost.

The department must partition the entire queue into one or more contiguous batches. Every instrument must belong to exactly one batch. Find the minimum possible sum of the setup and calibration costs of all batches.

Input

The first line contains two integers ~n~ and ~S~ (~1 \leq n \leq 5000~, ~0 \leq S \leq 10^9~), the number of instruments and the fixed setup cost per batch.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~), the calibration sizes of the instruments in queue order.

Output

Output a single integer: the minimum possible total cost to process all instruments.

Example

Input 1

5 3
4 1 5 9 2

Output 1

14

One optimal partition is ~[4, 1, 5]~, ~[9]~, and ~[2]~. Its three batch costs are ~8~, ~3~, and ~3~, for a total cost of ~14~.

Input 2

6 4
10 12 11 50 52 51

Output 2

14

One optimal partition is ~[10, 12, 11]~ and ~[50, 52, 51]~. Each batch has a setup cost of ~4~ and a calibration cost of ~3~, giving a total cost of ~14~.

Input 3

8 6
7 3 9 9 2 8 1 5

Output 3

32