题目描述

给定整数 $k$ 与长为 $n$ 的整数序列 $a_1,\dots,a_n$，其中 $1\le a_i\le k$，你可以任意重排序列 $a$，使得下面式子的值最大。

$$\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}[((j-1)k+a_j)-((i-1)k+a_i)] $$

求出这个最大可能的值。

输入格式

第一行输入两个整数表示 $n,k$。

第二行输入 $n$ 个整数表示 $a_1,\dots,a_n$。

输出格式

输出一行一个整数表示排序后诗歌优美度的最大可能值。

3 3
2 1 3

24

7 7
1 2 3 4 5 6 7

2022

10 1000000
1 1 10 100 1000 1000 10000 100000 1000000 1000000

1414915227

提示

样例 1 解释

重排为 $1,2,3$ 后可以得到最大值。

数据范围与限制

对于 $10\%$ 的数据，保证 $n\le6$；

对于 $30\%$ 的数据，保证 $n\le100$；

对于 $70\%$ 的数据，保证 $n\le10^3$；

对于所有数据，保证 $1\le n\le10^5$，$1\le a_i\le k\le 10^6$。