問題文
在高桥国 有 N 个空置房屋。空置的房子 1 到 N 用整数编号,从东到西呈直线延伸。 1 以公里为间隔排列。 换句话说 i 空置房屋位于某个参考点的正东位置。 i 沿着路走一公里。
在这个国家 M 一名家庭成员已搬家。 i 第一个家庭是 P_i 一家人。 这个 M 致家属 1 一一整理空置房屋。在这种情况下,同一所房子不应该分配给多个家庭。
您的目标是以最大化“居民之间的距离”的方式分配空置房屋。 “居民之间的距离”是指所有搬家的居民之间的距离。 2 该值是每个人居住的房屋之间的距离之和。
使用最优分布方法求“居民之间的距离”的最大值。
入力
输入是从标准输入按以下格式给出的
N M P_1 P_2 : P_M
- 1 第一行是一个整数,代表高桥县的空置房屋数量。 N(2 ≦ N ≦ 10^6) 和搬到高桥县的家庭数量 M(2 ≦ M ≦ min(N, 1,000)) 用空格分隔。
- 2 从线 M 行数过多 i 行中, i 第th个家庭的人数 P_i(1 ≦ P_i ≦ 100) 给出。
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- 2 ≦ N ≦ 10 的数据集 给出 10 点。 如果正确答案是满足
- 2 ≦ N ≦ 10^6的数据集,则进一步 给出 90 点。总共 100 点。
出力
将“驻留距离”的最大值设置为 在 1 行上输出。 在输出末尾插入换行符。
入力例1
4 3 1 1 2
出力例1
11
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
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
出力例2
9852