問題

異世界に転生したhitsujiくんはモンスター討伐をしようと考えています．

時刻 $i\:(1 \le i \le N)$ に行えるhitsujiくんの行動は以下のうちどれか1つだけです． なお時刻 $1$ における体力は $M$ とします．

• 体力が $1$ 以上のとき，モンスターを討伐し，体力を $1$ 減らし賞金 $A_i$ を得る．
• 休憩し，体力を $M$ にする．
• 何もしない．

hitsujiくんが得られる賞金の合計の最大はいくらですか．

制約

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^5$
• 入力はすべて整数

入力

出力

賞金の合計の最大を出力せよ．

例

入出力例1

5 2
5 3 7 9 2

21

• $i=1$ ではモンスターを討伐し，体力は $1$ になり賞金 $A_1=5$ を得ます．
• $i=2$ では休憩をし，体力は $2$ になります．
• $i=3$ ではモンスターを討伐し，体力は $1$ になり賞金 $A_3=7$ を得ます．
• $i=4$ ではモンスターを討伐し，体力は $0$ になり賞金 $A_4=9$ を得ます．
• $i=5$ では何もしません．

よって，$A_1+A_3+A_4=5+7+9=21$ を得られ，これが最大です．

入出力例2

13 3
48 15 12 55 66 82 96 4 42 26 59 13 26

472