Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Burning Midnight Oil

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne day a highly important task was commissioned to Vasya — writing a program in a night. The program consists of *n* lines of code. Vasya is already exhausted, so he works like that: first he writes *v* lines of code, drinks a cup of tea, then he writes as much as lines, drinks another cup of tea, then he writes lines and so on: , , , ...

The expression is regarded as the integral part from dividing number *a* by number *b*.

The moment the current value equals 0, Vasya immediately falls asleep and he wakes up only in the morning, when the program should already be finished.

Vasya is wondering, what minimum allowable value *v* can take to let him write not less than *n* lines of code before he falls asleep.

Input

The input consists of two integers *n* and *k*, separated by spaces — the size of the program in lines and the productivity reduction coefficient, 1 ≤ *n* ≤ 10^{9}, 2 ≤ *k* ≤ 10.

Output

Print the only integer — the minimum value of *v* that lets Vasya write the program in one night.

Examples

Input

7 2

Output

4

Input

59 9

Output

54

Note

In the first sample the answer is *v* = 4. Vasya writes the code in the following portions: first 4 lines, then 2, then 1, and then Vasya falls asleep. Thus, he manages to write 4 + 2 + 1 = 7 lines in a night and complete the task.

In the second sample the answer is *v* = 54. Vasya writes the code in the following portions: 54, 6. The total sum is 54 + 6 = 60, that's even more than *n* = 59.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 06:27:14 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|