B

One 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 $\text{[math]}$ lines, drinks another cup of tea, then he writes $\text{[math]}$ lines and so on: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , ...

The expression $\text{[math]}$ is regarded as the integral part from dividing number a by number b.

The moment the current value $\text{[math]}$ 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⁹, 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

Input

59 9

Output

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.

题解：找到一个合适的值V，

【一天，一个非常重要的任务被委托给Vasya--在一个晚上写一个程序。该程序由n行代码组成。Vasya已经耗尽，所以，他的作品就像是：第一，他写道v行代码，喝一杯茶，然后他尽可能多写为 $\text{[math]}$ 线，饮料一杯茶，然后他写道 $\text{[math]}$ 线等： $\text{[math]}$ ， $\text{[math]}$ ， $\text{[math]}$ ， ...

该表达式 $\text{[math]}$ 被视为从数字a除以数字b组成的组成部分。

当前值 $\text{[math]}$ 等于0 的那一刻，Vasya立即睡着了，他只在早上才醒来，当时程序应该已经完成。

Vasya很纳闷，有什么最小允许值v可以让他写不低于比ň行代码，他睡着了。】

【题析】：需要用二分查找

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     long long  n;
 6     int m;
 7     scanf("%lld %d",&n,&m);
 8     long long v;
 9     int flag = 0;
10     long long  vv;
11     long long mid;
12     long long left  = 0;
13     long long right = n; 
14     long long ans = n;
15     while(left <= right) {
16         mid = (left + right) / 2;
17         //printf("%lld %lld %lld
",left,right,mid);
18         long long  sum = mid;
19         int count = 0;
20         long long v = m;
21         int vv = mid/v;
22         while(vv){        
23             sum += vv;
24             count++;
25             v = v*m;
26             vv = mid/v;
27         }
28         if(flag == 1) break;
29         if(sum >= n) {
30             
31             ans = min(ans,mid);
32             right = mid - 1;
33             ans = min(ans,mid);
34         } else {
35             left = mid + 1;
36         }
37     }
38     printf("%lld
",ans);
39     return 0;
40 }