1264. Super Egg Drop

You have k identical eggs and a building with n floors. An egg breaks if dropped from above some unknown critical floor f (0 <= f <= n) and survives at or below it; a survived egg can be reused, a broken one cannot. Return the minimum number of drops needed to determine f with certainty in the worst case. The input is JSON {k, n}.

Input: JSON {k, n}.

Output: Integer — the minimum number of drops in the worst case.

Examples

Input: {"k":1,"n":2}
Output: 2
Explanation: One egg forces a linear scan.

Input: {"k":2,"n":6}
Output: 3
Explanation: Three drops suffice.

Input: {"k":3,"n":14}
Output: 4
Explanation: Four drops suffice.

Constraints

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

Asked by