P4870 [BalticOI 2009] Beetle (Day1).

**Translated from [BalticOI 2009](http://www.csc.kth.se/contest/boi/tasks.php) Day1 T1 “[Beetle](http://www.csc.kth.se/contest/boi/beetle.pdf)”.** A beetle is on a horizontal tree branch. Because it is obsessed with math, it feels like it is on the $x$ axis. On the same branch, there are $n$ drops of dew. Each drop contains $m$ units of water. Relative to the beetle’s position, their coordinates are $x_1, x_2, \dots, x_n$. Obviously, the sun will be blazing that day. Every unit of time, each drop of dew loses $1$ unit of water. The beetle suffers so much from the sun that whenever it touches a drop of dew, it can instantly drink it all. In each unit of time, it can move $1$ unit of distance. So you need to write a program that, given the coordinates of the dew drops, computes the **maximum** amount of water the beetle can drink.

The first line contains two integers, $n$ and $m$. The next $n$ lines each contain one integer, giving the coordinates $x_1, x_2, \dots, x_n$.

Output one line containing the maximum amount of water the beetle can drink.

Constraints: $0 \le n \le 300$, $1 \le m \le 1{,}000{,}000$, $-10{,}000 \le x_1, x_2, \dots, x_n \le 10{,}000$, and for all $i \ne j$, $x_i \ne x_j$. Translated by ChatGPT 5