Presidential elections will soon be held in the United States of Berland. There are two candidates for this responsible position: Uncle Sam and Uncle Frodo. You are an analyst at Uncle Sam's campaign headquarters and are tasked with helping him defeat a rival. It was not possible to inflate a newspaper scandal because of the opponent's obsession with throwing rings into the vents of volcanoes, so we will have to use mathematics.
It would seem that in order to win, it is necessary to convince more than half of those who came to the polls to vote for our candidate. It turns out that sometimes you need much less! In order to understand how this is possible, let's take a closer look at the voting procedure.
As you know, the United States of Berland is divided into several administrative regions of the first level — states. First, local elections are held in each of the states, as a result of which each state casts its vote for one of the candidates. If at least half of the states have chosen Uncle Sam, then he wins (in case of a tie, Uncle Sam has the advantage as the incumbent president), otherwise Uncle Frodo wins. All states, in turn, are made up of second-level administrative regions, each of which is represented by an elector from third-level administrative regions, and so on. The last level consists of individual residents of Berland. There are N inhabitants and K levels of administrative units in Berland. One of the key principles of this country is equality, so that any region of the i-th level is divided into the same number of regions of the next level (including the same number of citizens).
It so happened that it was you who was instructed to do the division into regions, that is, it is in your hands to determine exactly how many administrative units of the i-th level the (i−1)-th administrative unit is divided into.
You also have a powerful tool to influence people's choices — oil burles. To get one voter to vote for Uncle Sam, it is enough to give him a modest gift of one oil burl.
Unfortunately, initially all N inhabitants of the United States of Berland are going to vote for Uncle Frodo. It is required to determine the minimum number of oil burles that is enough to spend to win the election.
Input data format
The single input line contains two integers N and K (1 <= N <= 1015 , 1 <= K <= 10).
Output data format
It is required to print a single number — the minimum amount of oil burles that will have to be spent on election gifts with the best breakdown by region.
Examples
|
Enter |
Output |
|
9 2 |
4 |
|
12 3
|
2 |
Remark
Berland laws do not forbid a country to consist of one state, and a city — one resident. Similarly with other types of regions.
In Figure 1, the regions where Uncle Sam won are marked in black. On the lower level, the vertices corresponding to the bribed specific residents are depicted in black.