AT_bcu30_a.すごろく

在 Cybozu 员工之间，双六游戏流行起来了。

员工们玩的这款双六有 $N+1$ 个格子，每个格子按照前进的顺序依次编号为 $0, 1, \ldots, 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$ 格即可到达终点，则先正好前进达到终点，然后后退 $a_i - x$ 格（其中 $x$ 为距离终点的剩余格数）。

给定 $N$、$K$ 以及每回合前进的格数 $a_i$，请输出最终（在 $K$ 回合全部结束，或中途到达终点且结束游戏后）棋子所在的格子编号。

输入格式如下：

$N\ K\ a_1\ a_2\ \ldots\ a_K$

请输出棋子最后停留的格子编号。

数据范围

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

样例解释 1

一开始棋子放在 $0$。

• 第 $1$ 回合出 $5$，棋子移动到 $5$。
• 第 $2$ 回合出 $7$，棋子移动到 $10$，因为还有 $2$ 格可以行动，所以再退回到 $8$。
• 第 $3$ 回合出 $2$，棋子移动到 $10$，此时刚好到达终点，移动结束。

最终棋子停在 $10$。

由 ChatGPT 5 翻译