4061. HS 的 Eula

【题目背景】

Eula 是 Genshin impact 中的一位角色。

                               ——— 「优菈：闪灼的烛光」OST / Eula Theme Music EXTENDED

【题目描述】

HS 是 Eula's lover，他很想要 Eula 999，但是 HS 没有钱，他接到了一个任务，可以赚钱。

HS 在一个数轴上，初始在 $0$ 位置，有 $n$ 个位置上有钱，每到达位置 $x_i$ 可以获得一些钱（假设 HS 可以立即获得当前位置的所有钱，被拿走后钱就不会再出现了），HS 的速度为 $1 \ \mathrm{m/s}$。

初始每个 $x_i$ 位置上有 $m$ 块钱，每经过一秒每个位置上的钱就会减少 $1$，作为给 HS 的惩罚。注意，钱数不会为负。

HS 想要更多的钱去玩 Genshin impact，可是他在摆烂，于是任务就交给了你，请你找出 HS 可以获得的最多钱数。

【输入格式】

第一行两个整数 $n,m$，表示有 $n$ 个位置上有钱，初始钱数都为 $m$。

第二行 $n$ 个整数，第 $i$ 个整数 $x_i$ 表示 $x_i$ 位置上初始有 $m$ 块钱，保证所有 $x_i$ 互不相同。

【输出格式】

一个整数表示 HS 可以获得的最多钱数。

【样例输入】

3 15
6
-3
1

【样例输出】

25

【样例说明】

从 $0 \rightarrow 1 \rightarrow -3$，$ans = (15 - 1) + (15 - 4) = 25$。

【数据规模与约定】

对于 $60\% $ 的数据保证 $n \le 100,m \le 1000$。

对于 $100\% $ 的数据保证 $n\le 500,-10^6 \le x_i \le 10^6,m \le 10^9$。

【来源】

这是链接...

P4870 [BalticOI 2009 Day1] 甲虫