L. Lakes
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marcos has a piece of land that can contain several lakes, and he wants to take advantage of these bodies of water to place some boats. The land can be represented as a grid of dimensions $$$1 \times N$$$ where each of its $$$N$$$ cells is entirely made of either land or water. Each boat that can be obtained in the boat market has a length $$$k$$$ for some positive integer $$$k$$$, and can be placed on the land occupying $$$k$$$ consecutive water cells. It is not possible to place more than one boat in the same water cell.

Marcos can obtain as many boats as he wants, of any length he wants. However, for the landscape to look aesthetic and diverse, Marcos decided that all the boats he places on the land must have different lengths and be arranged in strictly increasing order from left to right.

For each boat that Marcos manages to place, he earns a profit $$$G$$$. However, Marcos is not satisfied with the distribution of his land, so he is willing to excavate some land cells so that they become water and thus be able to place more boats. Excavating the $$$i$$$-th cell of the grid has a variable cost $$$T_i$$$, since not all cells have the same amount of ground to excavate.

If Marcos wisely chooses which cells to excavate and where to place the boats, what is the maximum net profit he can achieve?

Input

The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$G$$$ ($$$1 \leq G \leq 10^9$$$), which indicate respectively the number of cells of the land and the profit for placing a boat.

The second line contains $$$N$$$ integers $$${T_1}, {T_2}, \ldots, {T_N}$$$ ($$$0 \leq T_i \leq 10^9$$$), such that $$$T_i=0$$$ if the $$$i$$$-th cell is water, or $$$T_i \ge 1$$$ if the cell is land and its excavation cost is $$$T_i$$$.

Output

A line with an integer, the maximum net profit that Marcos can achieve.

Examples
Input
6 5
0 8 0 4 0 6
Output
6
Input
4 1
2 2 2 2
Output
0
Input
10 2
0 0 0 0 8 0 0 7 0 0
Output
4
Input
1 314159265
0
Output
314159265
Note

In the first example, Marcos can excavate the fourth cell with cost $$$T_4=4$$$. In this case, he can place a boat of length $$$1$$$ in the first water cell, and another of length $$$3$$$ in the remaining water cells. His total profit for placing $$$2$$$ boats is $$$2 \cdot G = 2 \cdot 5 = 10$$$. Considering the excavation cost, his net profit is $$$10 - 4 = 6$$$.

In the second example, it is better for Marcos not to place any boats.