有 $N$ 栋编号为 $1$ 到 $N$ 的房屋。房屋 $i$ 和房屋 $j$ 之间的距离为 $|i - j|$。

你需要将 $M$ 个家庭分配到这些房屋中。第 $i$ 个家庭有 $P_i$ 个人。任何两个家庭不能被分配到同一栋房屋。

你的目标是最大化居民的距离。对于 $M$ 个家庭中任意两个人的（无序）对，计算他们房屋之间的距离。居民的距离定义为所有这些对的距离之和。

计算居民距离的最大可能值。

输入格式

$N \ M$ $P_1$ $P_2$ $\vdots$ $P_M$

数据范围

• $2 \le N \le 10^6$
• $2 \le M \le \min(N, 1000)$
• $1 \le P_i \le 100$

输出格式

在一行中输出答案。

样例

样例输入 1

4 3
1
1
2

样例输出 1

11

样例输入 2

10 10
3
1
4
1
5
9
2
6
5
3

样例输出 2

2998

样例输入 3

20 10
2
7
1
8
2
8
1
8
2
8

样例输出 3

9852

说明

在样例 1 中，设 A 为第一个家庭的成员，B 为第二个家庭的成员，C 和 D 为第三个家庭的成员。

在最优分配中，第一个家庭应前往房屋 1，第二个家庭应前往房屋 2，第三个家庭应前往房屋 4。

• A 和 B 之间的距离：1
• A 和 C 之间的距离：3
• A 和 D 之间的距离：3
• B 和 C 之间的距离：2
• B 和 D 之间的距离：2
• C 和 D 之间的距离：0

居民的距离为 11。