#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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* ≤ 10^{9}, *K* = 1 (i.e. the number of idols will **double** on step 3).

Subtask 4 (31%): 1 ≤ *N* ≤ 10^{9}. 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 21 | 10 | 1s | 256MB | Minimum |

2 | 23 | 46 | 1s | 256MB | Minimum |

3 | 25 | 30 | 1s | 256MB | Minimum |

4 | 31 | 116 | 1s | 256MB | Minimum |

5 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o idolclub -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512