Safe Drop Test

Time limit2sMemory limit128 MB

Summary

Given N floors and K identical safes, compute the minimum number of drops needed in the worst case to find the critical breaking floor.

Level: Medium6 of 10
Topics: Dynamic programming, Binary search, Math
Solved: No attempts yet

Problem

There is an N-story building. For some threshold floor F, dropping a safe from floor F or any higher floor always breaks it, while dropping it from any lower floor never breaks it. The safe may also survive a drop from floor N, and it may break starting from floor 1.

You have K identical safes and want to determine this threshold by dropping safes. A broken safe cannot be used again; a safe that does not break can be reused.

Let E(N, K) be the minimum number of drops needed to determine F in the worst case, no matter where F is. If K=1, you must test floors in increasing order until the safe would break, so E(N, 1)=N.

Given N and K, compute E(N, K).

Input

The first line contains two integers N(1 <= N <= 500) and K(1 <= K <= N).

Output

Print E(N, K) on the first line.

Examples3

Example 1
Input
```
4 2
```
Expected output
```
3
```
Example 2
Input
```
5 1
```
Expected output
```
5
```
Example 3
Input
```
8 3
```
Expected output
```
4
```