問題文

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

社員が遊んでいるすごろくは $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)$

入力

入力は以下の形式で与えられる。

$N$ $K$ $a_1$ ... $a_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