지수 교환

앨리스와 밥이 협력 게임을 하고 있다. 두 사람이 함께 가진 돈은 $b^p$ 달러이다. 여기서 $b$와 $p$는 주어진 정수이다. 앨리스는 처음에 $x$ 달러를 가지고, 밥은 $b^p - x$ 달러를 가진다. 두 사람은 돈을 한 사람에게 모아서 한 명이 전부 가지려고 한다.

거래 한 번에 한 사람이 상대에게 $b^y$ 달러를 보낼 수 있다. 이때 $y$는 $0 \le y < p$를 만족하는 정수이다. 각 사람은 자신이 시작하는 거래 수를 가능한 한 적게 하려고 한다. 두 사람은 거래를 가장 많이 시작하는 사람(가장 바쁜 사람)이 시작하는 거래 수가 가능한 한 적어지도록 협력한다.

앨리스와 밥은 돈을 모두 옮기는 데 가장 바쁜 사람이 시작해야 하는 거래 수의 최솟값을 알고 싶어 한다.

첫 줄에 두 정수 $b$ ($2 \le b \le 100$)와 $p$ ($2 \le p \le 1000$)가 주어진다. $b$는 진법의 밑이고, $p$는 자릿수이다.

다음 줄에는 공백으로 구분된 정수 $p$개 $x_{p-1}, x_{p-2}, \ldots, x_0$가 주어진다. 각 $x_i$는 $0 \le x_i < b$를 만족하고, $x_{p-1} > 0$이다. 이 값들은 $x$의 $b$진법 자릿수이며, 가장 높은 자리부터 순서대로 주어진다. 즉 $x = \sum_{0 \le i < p} b^i x_i$이다. 예를 들어 $b=10$일 때 4 2 7 8 6은 10진법 수 42786을 뜻한다.

돈을 앨리스 또는 밥 한 사람에게 모두 옮기는 데 필요한, 가장 바쁜 사람이 시작하는 거래 수의 최솟값을 정수 하나로 출력한다.