import functools

# floors - number of unchecked floors
# eggs - number of remaining eggs

# returns (moves, floor)
# where
#   moves - is the number of moves required to determine the floor in the worst scenario
#   floor - is the floor (1-based) from where you should drop the next egg

@functools.lru_cache(maxsize=None)
def solve(floors, eggs):
    if floors == 0:
        return 0, 0
    elif eggs == 1:
        return floors, 1
    else:
        acc = 999999
        drop = -1
        for i in range(floors):
            x, _ = solve(i, eggs - 1)
            y, _ = solve(floors - i - 1, eggs)
            a = max(x, y) + 1
            if a < acc:
                acc = a
                drop = i + 1
        return acc, drop