시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB222544028.777%

문제

팀파이트 매니저를 만든 팀 사모예드에서 신작을 만들고 있다. 이번 게임은 지폐를 화폐로 사용하고, 다음과 같은 규칙을 만족해야 한다.

  1. 지폐의 서로 다른 액면가는 K가지가 있다.
  2. 액면가가 가장 작은 지폐의 액면가는 1원이다.
  3. i번째 지폐의 액면가는 i-1번째 지폐의 액면가의 2, 3, 4, 5 배 중 하나이다.

이 게임을 시작할 때, 플레이어는 N원을 받고 시작하게 된다. 플레이어에게 지폐를 너무 많이 주면 리소스에 문제가 생길 수 있기 때문에, N원을 만드는 지폐의 개수를 최소로 하려고 한다. 두 정수 N과 K가 주어진다. 지폐 개수를 최소로 하는 액면가 구성을 찾고, 그 때 플레이어가 받게되는 지폐 개수의 최소값을 구해보자.

입력

첫째 줄에 두 정수 N과 K가 주어진다.

출력

첫째 줄에 N원을 만들 수 있는 최소 지폐의 수를 출력한다.

제한

  • 1 ≤ N ≤ 1018
  • 1 ≤ K ≤ 100

예제 입력 1

1025
6

예제 출력 1

2

액면가 구성을 1, 4, 16, 64, 256, 1024로 하면, 1025 = 1024 + 1로 만들 수 있다.

예제 입력 2

1005
5

예제 출력 2

3

1, 5, 25, 100, 500으로 액면가를 정하면 1005 = 2 × 500 + 5로 만들 수 있다.

예제 입력 3

12000
14

예제 출력 3

1

예제 입력 4

924323565426323626
1

예제 출력 4

924323565426323626

예제 입력 5

924323565426323626
50

예제 출력 5

10

출처