该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

小明实在没 IDEA 了，只会出简单题。

题目描述

小明最近在学习博弈论，博弈论里有一个很重要的函数：$\text{MEX}$。

$\text{MEX}(S)$ 表示非负整数集合 $S$ 中，没有出现过的最小的非负整数。

例如，$\text{MEX}(\{0,3,2,1,5\})=4,\text{MEX}(\{0,3,5,4,1\})=2$。

现在，小明有一个可重非负整数集合 $S$，数字范围在 $0,...,m$ 之间。

你需要帮助小明，从这个可重集中挑选出恰好 $n$ 个数字组成一个数组 $A$，最大化：

$\min\limits_{i=1}^{n-m+1}(\text{MEX}(l_i,r_{i+m-1}))$ ，也就是，对于数组 $A$ 所有长度为 $m$ 的区间，其 $\text{MEX}$ 中的最小值。

输入格式

第一行输入 $n,m$。

接下来一行共 $m+1$ 个非负整数，第 $i(0\leq i\leq m)$ 个整数 $a_i$ 表示可重集 $S$ 中共有 $a_i$ 个数字 $i$。

输出格式

输出一个数字表示答案。

样例输入 #1

5 4
2 1 1 1 1

样例输出 #1

4

样例解释 #1

可重集 $S=\{0,0,1,2,3,4\}$，我们可以构造 $A=[0,3,1,2,0]$，这样对于所有长度为 $4$ 的区间，其 $\text{MEX}$ 都等于 $4$。

样例输入 #2

10 6
2 2 3 3 2 5 2

样例输出 #2

6

下发文件

数据范围

对于全部测试数据：$1\leq n\leq 10^{18},1\leq m\leq \min(10^5,n),0\leq a_i\leq 10^{18},\sum a_i\geq n$。