26616번 - 통역사

문제

송죽국은 $N$개의 도시로 이루어져 있는 평화로운 국가이다. 각 도시는 1ドル$번, 2ドル$번, ..., $N$번과 같이 번호를 가지고 있다.

옛날에는 송죽국의 모든 도시가 공용어인 1ドル$번 언어를 사용했다고 전해진다. 그러나 시간이 흐름에 따라 도시마다 언어가 다르게 바뀌었다. 그 결과 지금 $i$번 도시는 $i+1$번 언어를 사용하게 되었다. 안타깝게도 1ドル$번 언어는 사어가 되어 아무도 구사할 수 없다.

어느 날, 송죽국의 $K$번 도시에 큰 사건이 일어났다. $K$번 도시의 시장은 이 사실을 다른 도시에 알리기로 했으나, 서로 다른 언어를 쓰는 두 도시가 말이 통하지 않는다는 문제에 부딪쳤다. 시장은 고민 끝에, $K$번 도시를 제외한 모든 도시에 대해서 $K$번 도시가 사용하는 언어를 그 도시가 사용하는 언어로 통역하는 $N-1$명의 통역사를 고용하기로 했다.

한 명의 통역사는 아래와 같은 과정을 통해 한 언어를 다른 언어로 통역한다. 이때, 양의 정수 $X$와 1ドル$보다 큰 정수 $b$에 대해 $X$의 $b$진법 표현 $[x_{j}, x_{j-1}, ..., x_{1}, x_{0}]$은 $X=x_{j}b^{j}+x_{j-1}b^{j-1}+...+x_{1}b+x_{0}$를 만족하는 정수 $x_{j}, x_{j-1}, ..., x_{1}, x_{0}$로 구성된 배열이다. $(0 \le x_{j}, x_{j-1}, ..., x_{1}, x_{0} < b, x_{j} \neq 0)$ $X$의 $b$진법 표현은 항상 유일하다.

• 양의 정수 $A$와 1ドル$보다 큰 정수 $p$에 대해, $A$의 $p$진법 표현 $[a_{k}, a_{k-1}, ..., a_{1}, a_{0}]$를 구한다.
• $\text{max} \{ a_{k}, a_{k-1}, ..., a_{1}, a_{0} \}$보다 큰 정수 $q$에 대해, $B$의 $q$진법 표현이 $[a_{k}, a_{k-1}, ..., a_{1}, a_{0}]$와 같아지는 양의 정수 $B$를 구한다.
• 통역사는 $A$번 언어를 $B$번 언어로 통역할 수 있으며, 이 통역사를 고용하는 데 드는 비용은 $p+q$이다.

예를 들어, 1ドル$번 도시가 사용하는 2ドル$번 언어를 2ドル$번 도시가 사용하는 3ドル$번 언어로 통역하기 위해 $A=2, p=2, B=3, q=3$을 선택할 수 있다. 2ドル$의 2ドル$진법 표현 $[1, 0]$과 3ドル$의 3ドル$진법 표현이 같기 때문이다. 그리고 이때 드는 비용은 2ドル+3=5$이다.

송죽국을 이루는 도시의 수 $N$과 사건이 일어난 도시의 번호 $K$가 주어졌을 때, $K$번 도시가 사용하는 언어를 나머지 도시가 사용하는 언어로 통역하는 $N-1$명의 통역사를 고용하는 최소 비용을 구하여라.

입력

첫 번째 줄에 두 양의 정수 $N,ドル $K$가 공백을 사이에 두고 주어진다. $(1 \le K \le N \le 10^{6})$

출력

첫 번째 줄에 $K$번 도시가 사용하는 언어를 나머지 도시가 사용하는 언어로 통역하는 $N-1$명의 통역사를 고용하는 최소 비용을 구해 출력한다.

제한

힌트