问题描述

高桥国有 $N$ 个空置房屋。这些房屋编号为从 $1$ 到 $N$ 的整数，并且按照相同的间隔在东西方向直线上排列，间隔为 $1$ 公里。也就是说，第 $i$ 个空置房屋位于某个参考点往东移动 $i$ 公里的地方。

这个国家有 $M$ 个家庭搬迁过来。第 $i$ 个家庭有 $P_i$ 个人。现在需要将这 $M$ 个家庭挨个分配给空置房屋，不能让多个家庭分配到同一个房屋。

你的目标是通过合理的分配空置房屋来最大化 "居民距离"。 "居民距离" 是指所搬迁的人群中的每对人员之间所住房屋距离的总和。

请计算当进行最佳分配时的 "居民距离" 的最大值。

输入

输入以以下格式从标准输入中给出

$N$ $M$ $P_1$ $P_2$ : $P_M$

• 第一行包含两个整数 $N (2 ≦ N ≦ 10^6)$ 和 $M (2 ≦ M ≦ \min(N, 1,000))$，分别表示空置房屋数量和搬迁到高桥国的家庭数量。
• 接下来的 $M$ 行中的第 $i$ 行包含一个正整数 $P_i (1 ≦ P_i ≦ 100)$，表示第 $i$ 个家庭的人数。

部分分

此问题设有部分分。

• 对于满足 $2 ≦ N ≦ 10$ 的数据集正确的答案将得到 10 分。
• 对于满足 $2 ≦ N ≦ 10^6$ 的数据集正确的答案将再获得额外 90 分。总共最多可得 100 分。

输出

输出 "居民距离" 的最大值，换行。

示例1

4 3
1
1
2

输出示例1

11

假设第一个家庭有 A 先生，第二个家庭有 B 小姐，第三个家庭有 C 先生和 D 小姐。如果将第一个家庭安排在第一个空置房屋，将第二个家庭安排在第二个空置房屋，将第三个家庭安排在第四个空置房屋，那么每一对人之间的距离如下：

• A 先生和 B 小姐的距离：1
• A 先生和 C 先生的距离：3
• A 先生和 D 小姐的距离：3
• B 小姐和 C 先生的距离：2
• B 小姐和 D 小姐的距离：2
• C 先生和 D 小姐的距离：0

因此，总和为 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