Exponent Exchange

Alice and Bob are playing a cooperative game. Together they hold $b^p$ dollars, where $b$ and $p$ are given integers. Alice initially holds $x$ dollars, and Bob holds $b^p - x$ dollars. Alice and Bob want to consolidate their money so that one person holds all of it.

In each transaction, one player can send the other player $b^y$ dollars, for some integer $y$ with $0 \le y < p$. Each player wants to initiate as few transactions as possible. They cooperate so that the player who initiates the most transactions (the busiest player) initiates as few as possible.

Alice and Bob want to know the fewest number of transactions that the busiest player must initiate to transfer all the money.

The first line contains two integers $b$ ($2 \le b \le 100$) and $p$ ($2 \le p \le 1000$), where $b$ is the base and $p$ is the number of digits.

The next line contains $p$ integers $x_{p-1}, x_{p-2}, \ldots, x_0$, separated by spaces, with $0 \le x_i < b$ and $0 < x_{p-1}$. These are the base-$b$ digits of $x$, given from the highest power to the lowest. That is, $x = \sum_{0 \le i < p} b^i x_i$. For example, with $b=10$, the digits 4 2 7 8 6 represent the number 42786.

Output a single integer: the minimum number of transactions that the busiest player must initiate to transfer all the money to either Alice or Bob.