問題文

高橋国には $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