問題文

大人気ピザ店の「Dynamic Pizza」(通称DP)には $M$ 種類のピザがあり、 $i$ 種類目のピザの美味しさは $A_i$ です。

Koi君は「Dynamic Pizza」でピザを$N$個食べることにしました。ただし、Koi君は飽き性なので、直前に食べたピザと同じ種類のピザを食べることができません。

食べたピザの美味しさの総和としてあり得るものの最大値を出力して下さい。なお、Koi君は今までピザを食べたことがないので、最初に食べるピザは自由に決めることができます。

制約

• $1 \leq N \leq 300$
• $2 \leq M \leq 300$
• $0 \leq A_i \leq 10^9 (1 \leq i \leq N)$

入力

入力はすべて整数である。

N M
A_1 A_2 ... A_M

出力

食べたピザの美味しさの総和としてあり得るものの最大値を整数で出力してください。

サンプル

2 3
8 7 7

15

例えば1種類目→3種類目の順に食べると、食べたピザの美味しさの総和は15になります。食べたピザの美味しさの総和を15より大きくすることはできないので15を出力してください。

5 4
1000000000 1000000000 1000000000 1000000000 1000000000

5000000000