Problem Statement

高橋国には $N$ 個の空き家がある。空き家は $1$ から $N$ の整数で番号付けされており、順に東西に一直線に $1$ キロメートル間隔で並んでいる。 つまり $i$ 番目の空き家は ある基準点から真東に $i$ キロメートル進んだところにある。

この国に $M$ 世帯の家族が引っ越してきた。 $i$ 番目の家族は $P_i$ 人家族である。 この $M$ 世帯の家族に $1$ 軒ずつ空き家を振り分けていく。このとき複数の家族に同じ家を振り分けてはならない。

あなたの目標は「住民の距離」を最大化するように空き家を振り分けることである。 「住民の距離」とは引っ越してきた人々の中の全ての $2$ 人組について、その住んでいる家の距離の総和を取った値である。

最適な振り分け方をしたときの「住民の距離」の最大値を求めよ。

Input

入力は以下の形式で標準入力から与えられる

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$ 点となる。

Output

「住民の距離」の最大値を $1$ 行に出力せよ。 出力の末尾に改行を入れること。