问题

在Cybozu的员工中，太空行走变得流行起来。

员工玩的太空行走有$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$个方格的位置到达终点（$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