Beetle

This problem is translated from BalticOI 2009 Day1 T1 "Beetle". A mathematically-obsessed beetle finds its horizontal branch identical to the x-axis. On the same branch there are n dewdrops. Each dewdrop initially contains m units of water and loses 1 unit per time unit. Their positions relative to the beetle are given as x₁, x₂, …, x_n.

The beetle, tormented by the blazing sun, can move at 1 unit per time unit and instantly drinks a dewdrop upon reaching it. When the beetle reaches a dewdrop at time t, it obtains \( m-t \) units of water if \( t<m \) (otherwise, 0). Your task is to determine the maximum total water the beetle can drink by planning an optimal route.

Note: The dewdrops dry out as time passes, so the order in which they are visited is crucial. The beetle starts at position 0 at time 0.

inputFormat

The first line contains two integers n and m, representing the number of dewdrops and the initial water content per dewdrop respectively.

The second line contains n integers: x₁, x₂, …, x_n, representing the positions (which may be negative, zero, or positive) of the dewdrops on the x-axis.

outputFormat

Output a single integer: the maximum total water the beetle can drink.

sample

3 10
-2 4 1

17