오락 고?

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

요약

1부터 i까지의 수를 차례로 적었을 때 숫자 K가 N번 이상 나타나는 가장 작은 i를 구합니다. N은 최대 1000자리입니다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 동적 계획법, 수학, 구현
정답자: 아직 제출이 없습니다

문제

오락실 리듬 게임에 중독된 현제는 특이한 습관을 갖고 있다. 현제가 마지막으로 게임을 하지 않은 날부터 세어서, 하루가 되면 노트에 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
```