D - 引っ越し Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋国には 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 番目の家族を構成する人数 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