시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 134 28 18 21.951%

문제

준규는 심심해서 보드게임을 만들었다. 너무 심심했기 때문에, 보드 게임에 사용되는 돈도 독특하게 만들었다. 

K개의 돈을 만드려고 한다. 첫 번째는 1원이다. 그 다음, 적절히 돈을 만든 다음 돈을 오름차순으로 정렬했을 때, i번째 돈이 i-1번째 돈의 2, 3, 4, 5배 중 하나를 만족하게 만드려고 한다.

이 보드게임을 시작할 때, 각 사람은 N원을 가지게 된다. 준규는 N원을 모든 플레이어에게 줄 때, 주는 지폐의 개수를 최소로 하려고 한다. 준규는 모든 종류의 지폐를 무한개 가지고 있다.

N과 K가 주어졌을 때, N을 만드는 지폐 개수의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K(1 ≤ N ≤ 1018, 1 ≤ K ≤ 100)가 주어진다.

출력

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

예제 입력

1025
6

예제 출력

2

힌트

돈을 {1,4,16,64,256,1024}로 만들면, 1025 = 1024+1 이 되어 2개로 가능하다.

출처