Bounty Hunter

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

時刻 に行えるhitsujiくんの行動は以下のうちどれか1つだけです． なお時刻 における体力は とします．

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

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

• 入力はすべて整数

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

5 2
5 3 7 9 2

21

• ではモンスターを討伐し，体力は になり賞金 を得ます．
• では休憩をし，体力は になります．
• ではモンスターを討伐し，体力は になり賞金 を得ます．
• ではモンスターを討伐し，体力は になり賞金 を得ます．
• では何もしません．

よって， を得られ，これが最大です．

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

472