Algorithms and Data Structures

Dangerous Experiments

You are given a building with n floors and k identical bottles. Each bottle can be dropped from any floor of the building and will break if dropped from or above a certain floor.
Your task is to determine the minimum number of attempts required to find the lowest floor from which the bottle will break when dropped, using the given bottles.
notion image

Input

The only line of the input contains two integers n (100 ≀ n ≀ 500) and k (1 ≀ k ≀ 30), representing the number of floors in the building and the number of bottles, respectively.

Output

Output a single integer, representing the minimum number of attempts required to find the lowest breaking floor, using the given number of bottles.

Examples

Input
Output
100 2
14

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in