Alice 和 Bob 正在进行一场合作游戏。给定整数 $b$ 和 $p$，他们总共拥有 $b^p$ 美元。 Alice 最初持有 $x$ 美元，Bob 持有 $b^p - x$ 美元。Alice 和 Bob 希望合并他们的资金，使得其中一人持有全部资金。

在每次交易中，一名玩家可以选择向另一名玩家发送 $b^y$ 美元，其中 $y$ 为满足 $0 \le y < p$ 的整数。 但每位玩家都希望发起的交易次数尽可能少。他们愿意合作，使得发起交易次数最多的那个人（最忙碌的玩家）所发起的交易次数尽可能少。

Alice 和 Bob 想知道，为了完成资金转移，最忙碌的玩家需要发起的最小交易次数是多少。

输入格式

第一行包含两个整数 $b$ ($2 \le b \le 100$) 和 $p$ ($2 \le p \le 1000$)，其中 $b$ 是基数，$p$ 是位数。

下一行包含 $p$ 个整数 $x_{p-1}, x_{p-2}, \dots, x_0$，以空格分隔，满足 $0 \le x_i < b$ 且 $0 < x_{p-1}$。这些是 $x$ 在基数 $b$ 下的数字，按从高位到低位的顺序给出。具体来说，$x = \sum_{0 \le i < p} b^i x_i$。注意，它们是按幂次从高到低给出的。例如，在样例中，$b = 10$ 时，$4\ 2\ 7\ 8\ 6$ 代表十进制数 $42786$。

输出格式

输出一个整数，表示为了将所有资金转移给 Alice 或 Bob 中的一人，最忙碌的玩家需要发起的最小交易次数。

样例

输入 1

10 5
4 2 7 8 6

输出 1

7