455. Worker's Egg Experiment

0

Hard

A worker is conducting an experiment with eggs. The worker has been given k identical eggs and has access to a building with n floors, labeled from 1 to n. The worker knows that there is a specific floor, denoted as f, where 0 <= f <= n. Any egg dropped from a floor higher than f will break, while any egg dropped from or below floor f will not break.
During each move, the worker can select an unbroken egg and drop it from any floor x, where 1 <= x <= n. If the egg breaks, it can no longer be used. However, if the egg does not break, the worker can reuse it in future moves.
The worker needs to determine the value of f with certainty and return the minimum number of moves required to do so.

Input Format

The input consists of two lines:
- The first line contains a single integer k, representing the number of identical eggs given to the worker.
- The second line contains a single integer n, representing the number of floors in the building.

Output Format

Return an integer value representing the minimum number of moves required to determine the value of f.

Example

Input

1
2

Output

2

Constraints

- 1 <= k <= 100
- 1 <= n <= 10^4

Loading...

View Submissions

Console