Problem Description

Translated from BalticOI 2009 Day1 T1 “Beetle”.

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.

Input Format

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 Format

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

3 15
6
-3
1

25

Hint

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