AT_arc043_d.[ARC043D] 引っ越し

题目大意

高桥乡有 $N$ 间空置房。空房的整数编号从 $1$ 到 $N$，从东到西按 $1$ 千米的间隔依次排成一条直线。因此，第 $i$ 幢空房位于参考点正东方向的 $i$ 公里处。

$M$ 个家庭搬到了这个国家。第 $i$ 个家庭有 $P_i$ 名成员。这 $M$ 个家庭分别分配到 $1$ 套空房。目前，同一房屋不应分配给多个家庭。

您的目标是以最大化"居民距离"的方式分配空房。"居民距离"是所有 $2$ 对已搬进房屋的人的距离总和。

求最优排序的 "居民距离 "的最大值。

通过标准输入流输入，格式如下

$N$ $M$

$P_1$

$P_2$

:

$P_M$

• $1$ 行中的整数 $N(2 \leq N \leq 10^6)$ 代表高桥乡空置房屋数量，$M(2 \leq M \leq \min(N, 1000))$ 代表迁入高桥乡的家庭数量，以空格分隔。
• 在第 $2$ 至 $i$ 中，给出了第 $i$ 个家庭的人数 $P_i(1 ≦ P_i ≦ 100)$。

部分分

本题设置了部分分数。

• 正确回答满足 $2 \leq N \leq 10$ 的数据可得 $10$ 分。
• 正确回答满足 $2 \leq N \leq 10^6$ 的数据将获得额外的 $90$ 分。总分为 $100$。

将 "居民距离 "的最大值输出到 $1$ 行。在输出结束时换行。

样例 1 解释

第 $1$ 个家庭由 A 先生组成。第 $2$ 个家庭由 B 先生组成。第 $3$ 个家庭由 C 先生和 D 先生组成。 如果我们把第 $1$ 个家庭分配到第 $1$ 栋空房，把第 $2$ 个家庭分配到第 $2$ 栋空房，把第 $3$ 个家庭分配到 $4$ 栋空房，那么每对人之间的距离如下。

• A 先生与 B 先生之间的距离： $1$。
• A 先生与 C 先生之间的距离： $3$。
• A 先生和 D 先生之间的距离： $3$。
• B 先生与 C 先生之间的距离： $2$。
• B 先生与 D 先生之间的距离： $2$。
• C 先生与 D 先生之间的距离： $0$。

因此，总计为 $11$。这就是 "居民距离 "的最大值。