Problem Description

Sugoroku is popular among the employees at Cybozu.

The sugoroku board the employees are playing on consists of $ N+1 $ squares, each numbered sequentially from $ 0 $ to $ N $ as you move forward. The starting square is numbered $ 0 $ and the goal square is numbered $ N $.

To get used to this sugoroku, you are practicing moving a piece alone. Before actually moving the piece, you decide how many squares $ a_i $ (where $1 \leq i \leq K$) you will move in each of the $ K $ turns. You then place the piece on the starting square. You decide to move the piece according to the following rules:

Actions to be taken on the $ i $th turn ($1 \leq i \leq K$):

• If moving the piece $ a_i $ squares does not reach the goal, move the piece $ a_i $ squares.
• If moving the piece exactly $ a_i $ squares reaches the goal, move the piece $ a_i $ squares to the goal and end the game without performing the remaining turns.
• If moving less than $ a_i $ squares reaches the goal, move to the goal square exactly $ x $ squares away, then move back $ a_i - x $ squares.

Given $ N $, $ K $, and $ a_i $, determine the number of the square the piece is on after all $ K $ turns or when the game ends by reaching the goal.

Input Format

The input is given in the following format:

$ N $ $ K $ $ a_1 $ ... $ a_K $

Output Format

Output the number of the square the piece is on after all turns or when the game ends.

Sample Input and Output

Sample Input #1

10 4
5 7 2 5

Sample Output #1

10

Sample Input #2

10 4
5 7 3 5

Sample Output #2

6

Sample Input #3

20 7
12 5 5 15 2 10 20

Sample Output #3

1

Notes/Hints

Constraints

• $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

The piece is initially placed on square $ 0 $.
- On the 1st turn, $ 5 $ is rolled, so the piece moves to square $ 5 $.
- On the 2nd turn, $ 7 $ is rolled, so the piece moves to square $ 10 $, which is the goal, but there are still $ 2 $ squares left to move, so it moves back to square $ 8 $.
- On the 3rd turn, $ 2 $ is rolled, so the piece moves to square $ 10 $, exactly reaching the goal, and the movement stops here.
The piece is finally on square $ 10 $.

见题面 Input 部分

见题面 Output 部分