题目描述

给定整数 $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

7 7
1 2 3 4 5 6 7

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

1414915227

重排为 $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$ 。