문제 하나 풀어볼래?

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

요약

주어진 K와 C에 대해, K를 K번 쓰는 대신 K+A를 K+A번 쓸 때 절약되는 문자 수에서 C 곱하기 A를 뺀 값을 최대로 하는 양의 정수 A를 찾는다.

난이도: 어려움10점 중 9점
유형: 문자열 매칭, 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

인섭: 어떤 문제?
현우: 11을 11번 쓰려면 몇 글자가 필요할까?
인섭: 11은 두 자리 수니까... $2 \times 11 = 22$ !
현우: 틀렸어. 12자리면 충분해. 111111111111을 쓰면 11이 연속된 부분 문자열로 11번 등장하거든.
인섭: 미안해, 공부할게...
현우: 그러면 $K$ 가 $K$ 번 등장하는 가장 짧은 문자열을 내일까지 써 와.

인섭이는 현우가 낸 과제를 시작하려 한다. 하지만 $K$ 를 $K$ 번 쓰는 일은 너무 힘들었다. 어떻게 할까 고민하던 인섭이에게 좋은 아이디어가 하나 떠올랐다. $K + A$ ( $A > 0$ )가 $K + A$ 번 등장하는 문자열을 쓰고, 더 큰 수가 더 많이 등장했으니 원래 과제보다 어려운 문제를 풀어 왔다고 현우를 설득하는 것이다. 이 과정에서 써야 하는 글자 수가 $L$ 만큼 줄어들면 인섭이는 $L$ 만큼의 만족도를 얻는다.

하지만 인섭이는 현우가 낸 과제를 정확하게 해결하지 않는 데 양심의 가책을 느낀다. $K$ 를 $K$ 번 쓰는 대신 $K + A$ 를 $K + A$ 번 적는다면 $A$ 에 비례해 양심의 가책을 느낀다. 정확히는 어떤 상수 $C$ 에 대해 $C \times A$ 만큼의 가책을 느낀다.

인섭이는 얻은 만족도에서 양심의 가책을 뺀 값을 최대로 만들려 한다. 이 값이 얼마인지 찾아주자.

인섭이가 작성할 문자열에는 수가 겹쳐서 등장할 수도 있다. 예를 들어 문자열 12312312에는 12312가 2번 등장하며, 333333에는 3333이 3번 등장한다.

입력

문제에서 설명한 정수 $K$ 와 $C$ 가 공백으로 구분되어 주어진다. ( $1 \le K \le 10^{12}$ , $0 \le C \le 10^5$ )

출력

문제의 정답을 한 줄에 출력한다. 모든 양의 정수 $A$ 에 대해 값이 0 이하라면 0을 출력한다.

힌트

$K = 10$ , $C = 2$ 인 경우를 보자. 10을 10번 쓰면 모두 20글자를 써야 한다. 하지만 11을 11번 쓰면 12글자만 쓰게 되고, 이때 만족도는 8, 양심의 가책은 $(11 - 10) \times 2$ 가 되어 정답은 $8 - 2 = 6$ 이다.

예제3

예제 1
입력
```
10 2
```
예상 출력
```
6
```
예제 2
입력
```
1 0
```
예상 출력
```
0
```
예제 3
입력
```
12 0
```
예상 출력
```
1
```