AT_bcu30_a すごろく

[problemUrl]: https://atcoder.jp/contests/bcu30/tasks/bcu30_a サイボウズの社員の間では、すごろくが流行っています。 社員が遊んでいるすごろくは $ 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 $ ターンを全て終えるか、途中でゴールに到着しゲームを終了した時) 駒が置かれているマスの番号を求めてください。

入力は以下の形式で与えられる。 > $ N $ $ K $ $ a_1 $ ... $ a_K $

最終的に駒が置かれているマスの番号を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^9 $ - $ 1\ \leq\ K\ \leq\ 1000 $ - $ 1\ \leq\ a_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ K) $ ### Sample Explanation 1 はじめに駒は $ 0 $ に置かれています。 - $ 1 $ ターン目に $ 5 $ が出たので、駒は $ 5 $ に動きます。 - $ 2 $ ターン目に $ 7 $ が出たので、駒は $ 10 $ に動き、まだ $ 2 $ マス動けるので、 $ 8 $ に戻ります。 - $ 3 $ ターン目に $ 2 $ が出たので、駒は $ 10 $ に動き、ちょうどゴールに到着したので、ここで移動をやめます。 最終的に $ 10 $ に駒が置かれています。