問題文

サイボウズの社員の間では、すごろくが流行っています。

社員が遊んでいるすごろくは N+1 マスからなり、それぞれのマスには進む順に番号 0, 1, ... N がつけられています。 スタートのマスの番号は 0 、ゴールのマスの番号は N です。

あなたは、このすごろくに慣れるために、一人で駒を動かす練習をしています。 実際に駒を動かす前に K 回のターンで進めるマスの数 a_i (1 \leq i \leq K) を決め、スタートのマスに駒を置きました。 以下のようなルールに従って、実際に駒を動かすことにしました。

i ターン目 (1 \leq i \leq K) に行う動作

• 駒を a_i マス進めてもまだゴールに到達しないときは、駒を a_i マス進める。
• 駒をちょうど a_i マス進めるとゴールに到着するときは、駒を a_i マス進めてゴールに到着し、残りのターンを行わずにゲームを終了する。
• 駒を a_i マス未満進めるだけでゴールに到達できるときは、ゴールまで x マスちょうどで到達できるとき、ゴールまで移動し、その後 a_i - x マス戻る。

N 、 K および a_i があたえられるので、最終的に (K ターンを全て終えるか、途中でゴールに到着しゲームを終了した時) 駒が置かれているマスの番号を求めてください。

制約

• 1 \leq N \leq 10^9
• 1 \leq K \leq 1000
• 1 \leq a_i \leq N (1 \leq i \leq K)

入力例 1

10 4
5 7 2 5

出力例 1

10

はじめに駒は 0 に置かれています。

• 1 ターン目に 5 が出たので、駒は 5 に動きます。
• 2 ターン目に 7 が出たので、駒は 10 に動き、まだ 2 マス動けるので、 8 に戻ります。
• 3 ターン目に 2 が出たので、駒は 10 に動き、ちょうどゴールに到着したので、ここで移動をやめます。

最終的に 10 に駒が置かれています。

入力例 2

10 4
5 7 3 5

出力例 2

6

入力例 3

20 7
12 5 5 15 2 10 20

出力例 3

1