Problem Description
Fan Pu is the manager of a new idol club!
Fan Pu desires to have exactly N members in his idol club. The idol club has 0 idols at first. To recruit idols, Fan Pu will go idol scouting over a period of time.
Below is how a typical day of idol scouting works:
1. Fan Pu wakes up in the morning and checks how many idols there are in his club. If there are exactly N idols, he terminates the scouting process and will no longer go scouting.
2. Every idol in Fan Pu's club will recruit K new idols using their influence. That is to say, the number of idols in Fan Pu's club will increase by (K + 1) times.
3. Then, Fan Pu can personally recruit some idols to his club. He can recruit as few as 0 idols, and as many as N idols.
4. Fan Pu then goes to bed and repeats the process from step 1.
As Fan Pu is a lazy manager, and convincing new idols to join his club is a tough job, he wants to personally recruit as few idols as possible.
What is the least number of idols Fan Pu needs to personally recruit, in order to have exactly N idols in his club?
Input
The first line of input contains two integers N and K, the number of idols Fan Pu desires to have, and the number of new idols each existing idol will recruit.
Output
Output a single integer, the least number of idols Fan Pu must personally scout.
Limits
Subtask 1 (21%): 1 ≤ N ≤ 10. K = 1 (i.e. the number of idols will double on step 3).
Subtask 2 (23%): 1 ≤ N ≤ 10. 1 ≤ K ≤ N - 1.
Subtask 3 (25%): 1 ≤ N ≤ 109, K = 1 (i.e. the number of idols will double on step 3).
Subtask 4 (31%): 1 ≤ N ≤ 109. 1 ≤ K ≤ N - 1.
Subtask 5 (0%): Sample Testcases
Sample Testcase 1
Input
8 1
Output
1
Explanation
To have exactly 8 idols, Fan Pu needs to do the following:
Day 1
1. There are 0 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.
Day 2
1. There is 1 idol.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 2 idols now.
3. Fan Pu recruits 0 new idols. There are still 2 idols now.
4. Fan Pu goes to bed.
Day 3
1. There are 2 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 4 idols now.
3. Fan Pu recruits 0 new idols. There are still 4 idols now.
4. Fan Pu goes to bed.
Day 4
1. There are 4 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 8 idols now.
3. Fan Pu recruits 0 new idols. There are still 8 idols now.
4. Fan Pu goes to bed.
Day 5
1. There are 8 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 1 idol in total personally in the process.
Sample Testcase 2
Input
7 1
Output
3
Explanation
To have exactly 7 idols, Fan Pu needs to do the following:
Day 1
1. There are 0 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.
Day 2
1. There is 1 idol.
3. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 2 idols now.
2. Fan Pu recruits 1 new idol. There are 3 idols now.
4. Fan Pu goes to bed.
Day 3
1. There are 3 idols.
2. Each existing idol recruits 1 new idol. The number of idols increases by 2 times (i.e. double). There are 6 idols now.
3. Fan Pu recruits 1 new idol. There are 7 idols now.
4. Fan Pu goes to bed.
Day 4
1. There are 7 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 3 idols in total personally in the process.
Sample Testcase 3
Input
17 2
Output
5
Explanation
To have exactly 17 idols, Fan Pu needs to do the following:
Day 1
1. There are 0 idols.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are still 0 idols.
3. Fan Pu recruits 1 new idol. There is 1 idol now.
4. Fan Pu goes to bed.
Day 2
1. There is 1 idol.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are now 3 idols.
3. Fan Pu recruits 2 new idols. There are 5 idols now.
4. Fan Pu goes to bed.
Day 3
1. There are 5 idols.
2. Each existing idol recruits 2 new idols. The number of idols increases by 3 times (i.e. triple). There are now 15 idols.
3. Fan Pu recruits 2 new idols. There are 17 idols now.
4. Fan Pu goes to bed.
Day 4
1. There are 17 idols. Fan Pu sees that he has achieved the desired number of idols and terminates the scouting process. Fan Pu has recruited 5 idols in total personally in the process.