27578번 - Exponent Exchange 다국어

문제

Alice and Bob are playing a cooperative game. They hold $b^p$ dollars between them, for given integers $b$ and $p$. Alice initially holds $x$ dollars, and Bob holds $b^p - x$ dollars. Alice and Bob want to consolidate their money, so one person holds all the money.

In each transaction, one player can choose to send the other player $b^y$ dollars, for some integer $y$ with 0ドル \le y < p$. But each player wants to initiate as few transactions as possible. They are willing to cooperate such that the player that 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 needs to initiate to complete the transfer.

입력

The first line of input 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 the value of $x,ドル with the most significant digit first. Specifically, $x=\sum_{0\le i<p} b^i x_i$. Note that they are given in order from the highest power to the lowest. For example, in the sample, 4 2 7 8 6 with $b=10$ represents the base 10ドル$ number 42ドル,786円$.

출력

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

제한

힌트