오락 고?

시간 제한1초메모리 제한1024 MB

요약

1부터 d까지의 십진수 표기를 모두 이어 붙였을 때 숫자 K가 N번 이상 나타나는 최소의 d를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

오락실 리듬 게임에 중독된 현제는 특이한 습관을 갖고 있다. 현제는 마지막으로 게임을 하지 않은지 하루가 되면 노트에 1을 적고, 이틀이 되면 2를 적고, 이와 같은 방식으로 $i$ 일차가 되면 노트에 십진수로 $i$ 를 적는다. 현제가 게임을 하게 되면 노트에 적혀 있던 숫자들을 모두 지운다.

특이한 습관을 갖고 있는 현제는 금단증상마저 특이하다. 노트에 숫자 $K$ 가 $N$ 개 이상 적힌 경우, 현제는 자신이 녹화한 게임 영상을 돌려보면서 "오락 고?"를 외치는 버릇이 있다. 현제의 금단증상을 못마땅해 하던 동우는 현제가 게임을 하지 않은지 며칠이 지나야 금단증상이 오는지 확인하고 싶어졌다. 동우를 도와 현제가 금단증상이 오기 시작하는 데 걸리는 일 수를 구해보자.

입력

첫 번째 줄에 정수 $N$ ( $1 \le N \le 10^{1000} - 1$ )과 $K$ ( $0 \le K \le 9$ )가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 현제가 금단증상이 오기 시작하는데 걸리는 일 수를 출력한다.

예제3

예제 1
입력
```
2 0
```
예상 출력
```
20
```
예제 2
입력
```
3 1
```
예상 출력
```
11
```
예제 3
입력
```
9999999999 9
```
예상 출력
```
9999999999
```