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$。这就是 "居民距离 "的最大值。

### 部分点 この問題には部分点が設定されている。 - $ 2\ ≦\ N\ ≦\ 10 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - $ 2\ ≦\ N\ ≦\ 10^6 $を満たすデータセットに正解した場合はさらに $ 90 $ 点が与えられる。合計で $ 100 $ 点となる。 ### Sample Explanation 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 $ となる。これが「住民の距離」の最大値である。