Food Poisoning

Time limit1sMemory limit1024 MB

Summary

Find the fewest weeks of meals, each a subset of n restaurants, that pin down the single bad restaurant while poisoning Mikey at most p times.

Level: Medium6 of 10
Topics: Math, Combinatorics
Solved: No attempts yet

Problem

Your friend Mikey has been getting food poisoning every week lately. He is pretty sure the poisoning comes from exactly one restaurant, but he does not know which one. Mikey wants to find it as quickly as possible, in the fewest weeks.

Each week he can eat at any subset of his usual restaurants. The subset can be as small or as large as needed. Mikey does not want to get poisoned too many times, so he wants to find the bad restaurant while getting poisoned at most p times.

If Mikey eats at a subset in a given week and gets poisoned, the bad restaurant is in that subset. If he does not get poisoned, the bad restaurant is not in that subset. The subsets for different weeks do not have to be the same size.

Input

There is one input line with two integers: $n$ ( $1 \le n \le 100,000$ ), the number of restaurants, and $p$ ( $1 \le p \le 10,000$ ), the maximum number of times Mikey is willing to get food poisoning.

Output

Print the least number of weeks Mikey needs to eat before he can definitively determine the restaurant causing the food poisoning, using an optimal strategy against the worst case. There is always an answer.

Hint

With 8 restaurants and p = 1, Mikey can eat at one restaurant each week. That tells him whether that restaurant is the cause. Since there are only 8 restaurants, he knows the bad one after at most 7 weeks.

Examples2

Example 1
Input
```
8 1
```
Expected output
```
7
```
Example 2
Input
```
7 2
```
Expected output
```
3
```