Arcade Go?

Time limit1sMemory limit1024 MB

Summary

Find the smallest day count i such that writing the numbers 1 through i contains digit K at least N times, where N can have up to 1000 digits.

Level: Medium6 of 10
Topics: Binary search, Dynamic programming, Math, Implementation
Solved: No attempts yet

문제

Hyunje is addicted to a rhythm game at the arcade and has an unusual habit. Counting from the last day he played, on day 1 of not playing he writes 1 in his notebook, on day 2 he writes 2, and so on. On day $i$ he writes the decimal number $i$ . When Hyunje plays the game, he erases all the numbers in the notebook.

Hyunje's withdrawal symptoms are unusual too. When the digit $K$ appears at least $N$ times in the notebook, Hyunje rewinds the recordings of his games and shouts "Arcade go?" Dongwoo, who disapproves of these symptoms, wants to know how many days Hyunje must go without playing before the symptoms start. Help Dongwoo find the number of days until Hyunje's withdrawal symptoms begin.

입력

The first line contains two integers $N$ ( $1 \le N \le 10^{1000} - 1$ ) and $K$ ( $0 \le K \le 9$ ), separated by a space.

출력

On the first line, print the number of days until Hyunje's withdrawal symptoms begin.

Examples3

Example 1
Input
```
2 0
```
Expected output
```
20
```
Example 2
Input
```
3 1
```
Expected output
```
11
```
Example 3
Input
```
9999999999 9
```
Expected output
```
9999999999
```