문제 하나 풀어볼래?

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

어려움9문자열 매칭수학정수론그리디아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

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

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

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

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

입력

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

출력

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

힌트

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