You are given K eggs, and you have access to a building with N floors from 1 to N. 
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). 
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
 



Example 1:
Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.


Example 2:
Input: K = 2, N = 6
Output: 3


Example 3:
Input: K = 3, N = 14
Output: 4

 
Note:

1 <= K <= 100
1 <= N <= 10000

Difficulty: interview

Starter code:

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        

Solutions:
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def f(t):
            a=0
            r=1
            for i in range(1, K+1):
                r *= (t-i+1)
                r//=i
                a+=r
                if a>=N: 
                    break
            return a
        
        l, h= 1, N
        while l<h:
            m=(l+h)//2
            if f(m)<N:
                l=m+1
            else:
                h=m
        return l

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def aux(t, k):
            ret = 0
            r = 1
            for i in range(1, K+1):
                r *= t-i+1
                r //= i
                ret += r
                if ret >= N:
                    break
            return ret
        
        l, r = 1, N
        while l < r:
            m = (l + r) // 2
            if aux(m, K) < N:
                l = m+1
            else:
                r = m
        return l
    
#         memo = {}
#         def dp(n, k):
#             if (n, k) not in memo:
#                 if n == 0:
#                     ret = 0
#                 elif k == 1:
#                     ret = n
#                 else:
#                     lo, hi = 1, n
#                     while lo+1 < hi:
#                         x = (lo + hi) // 2
#                         t1 = dp(n-x, k)
#                         t2 = dp(x-1, k-1)
#                         if t1 < t2:
#                             hi = x
#                         elif t1 > t2:
#                             lo = x
#                         else:
#                             lo = hi = x
#                     ret = 1 + min(max(dp(n-x, k), dp(x-1, k-1)) for x in (lo, hi))
                
#                 memo[n, k] = ret
#             return memo[n, k]
        
#         return dp(N, K)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
            # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
            M = 300 # big enough number
            dp = [[0 for j in range(K+1)] for i in range(M+1)]
            # Initialization 1 --> no move no floor --> dp[0][*] = 0
            # Initialization 2 --> no egg no floor --> dp[*][0] = 0
            # General case --> we want to find dp[m][k] --> we pick one egg and drop (1 move)
            #              --> now we have k or k-1 eggs, depending on whether the previous egg is broken
            #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
            for i in range(1, M+1):
                for j in range(1, K+1):
                    dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
                    if dp[i][j] >= N:
                        return i

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (N+1) for _ in range(K+1)]
        # dp[k][n]: the max floor number we can cover with k eggs and n drops
        # if k = 1, dp[1][n] = n
        # if k >= 2, after one drop, n-1 drops left, two cases:
        #            if the egg breaks, k-1 egges, thus dp[k-1][n-1]
        #            if it doesn't break, k egges, thus dp[k][n-1]
        # just leave the 0 col and 0 row blank
        # when k = 1
        # when k >= 2
        for k in range(1, K+1):
            for n in range(1, N+1):
                if k == 1:
                    dp[k][n] = n
                else:
                    dp[k][n] = 1 + dp[k-1][n-1] + dp[k][n-1]
        # find the smallest n in the last row with dp[K,n] > N
        top, bott = 0, N
        while top < bott:
            mid = (top + bott) // 2
            if dp[K][mid] < N:
                top = mid + 1
            else:
                bott = mid
        return bott   
                


from functools import lru_cache

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # time complexity: O(K*N*logN)
        # space complexity: O(K*N)
        @lru_cache(None)
        def dp(k, n): # k eggs, n floors
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            if k > math.log(n, 2): return 1 + int(math.log(n,2))
            l, r = 1, n + 1
            while l < r:
                m = l + (r - l) // 2
                if dp(k-1, m-1) >= dp(k, n-m):
                    r = m
                else:
                    l = m + 1
            return 1 + max(dp(k-1, l-1), dp(k, n-l))
        
        return dp(K, N)

from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            if k > log(n, 2): return 1 + int(log(n, 2))
            l, r = 1, n + 1
            while l < r:
                m = l + (r - l) // 2
                if dp(k-1, m-1) < dp(k, n-m):
                    l = m + 1
                else: 
                    r = m
            return max(1 + dp(k-1, l-1), 1 + dp(k, n-l))
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        # dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

        dp = list(range(N+1))
        for i in range(2, K+1):
            k = 1
            temp =[0] + [N + 1] * (N)
            for j in range(1, N+1):
                while k < j+1 and temp[j-k] > dp[k-1]:
                    k += 1
                temp[j] = 1 + dp[k-1]
                # if i > j:
                #     dp[i][j] = dp[i-1][j]
                # else:
                #     val = N + 1
                #     for k in range(1, j+1):
                #         val = min(val, 1 + max(dp[i-1][k-1], dp[i][j-k]))
                #     dp[i][j] = val
            dp = temp[:]
        # print(dp)
        return dp[-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        # dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

        dp = list(range(N+1))
        for i in range(2, K+1):
            k = 1
            temp =[0] + [float('inf')] * (N)
            for j in range(1, N+1):
                while k < j+1 and temp[j-k] > dp[k-1]:
                    k += 1
                temp[j] = 1 + dp[k-1]
                # if i > j:
                #     dp[i][j] = dp[i-1][j]
                # else:
                #     val = N + 1
                #     for k in range(1, j+1):
                #         val = min(val, 1 + max(dp[i-1][k-1], dp[i][j-k]))
                #     dp[i][j] = val
            dp = temp[:]
        # print(dp)
        return dp[-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp = range(N+1)
        for i in range(2, K+1):
            k = 1
            temp =[0] + [N + 1] * (N)
            for j in range(1, N+1):
                while k < j+1 and temp[j-k] > dp[k-1]:
                    k += 1
                temp[j] = 1 + dp[k-1]
            dp = temp[:]
        return dp[-1]   

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        self.memo = {}

        return self.cal_eggs(K, N)

    def find_that_floor(self,K,N):
        left, right = 1, N
        while (left <= right):
            mid = (left + right) // 2
            # if it breaks;
            r1 = 1 + self.cal_eggs(K - 1, mid - 1)
            # if it not breaks;
            r2 = 1 + self.cal_eggs(K, N - mid)

            if r1 == r2:
                right = mid; break;
            elif r1 < r2:
                left = mid + 1
            else:
                right = mid - 1

        return right

    def cal_eggs(self, K, N):
        # print(K,N)
        if N == 0: return 0
        if K == 1: return N

        if (K, N) in self.memo:
            pass
        else:
            r = 2 ** 32 - 1
            now_floor = self.find_that_floor(K,N)
            for floor in range(now_floor, min(now_floor + 2,N+1)):
                # if it breaks;
                r1 = 1 + self.cal_eggs(K - 1, floor - 1)
                # if it not breaks;
                r2 = 1 + self.cal_eggs(K, N - floor)

                r = min(r, max(r1, r2))

            self.memo[(K, N)] = r

        return self.memo[(K, N)]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        max_floors = [[0 for _ in range(N + 1)] for _ in range(K + 1)]

        for k in range(1, K + 1):
            for t in range(1, N + 1):
                max_floors[k][t] = 1 + max_floors[k - 1][t - 1] + max_floors[k][t - 1]
        for t in range(N):
            if max_floors[K][t] >= N:
                return t
        return N


class Solution:
    def f(self, pivot: int, eggs: int, floors: int) -> int:
        
        ans, r = 0, 1        
        
        for idx in range(1, eggs+1):
            r *= (pivot - idx+1)
            r //= idx
            ans += r
            
            if ans >= floors:
                break
        
        return ans
    
    def superEggDrop(self, eggs: int, floors: int) -> int:
        
        lo, hi = 1, floors
        
        while lo < hi:
            
            mi = (lo + hi) // 2
            
            if self.f(mi, eggs, floors) < floors:
                lo = mi + 1
            else:
                hi = mi
        
        return lo

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            #min number of drops to make with given i eggs and j floors
            if j==0: return 0 
            if i==1: return j
            if j==1: return 1
            # print(i, j)
            
            
            #get min value for max(dp(i-1, k-1), dp(i, j-k)) 
            
            #play with k untill 
            
            lo, hi = 1, j
            
            while lo < hi:
                k = lo + (hi-lo)//2
                if dp(i-1, k-1) < dp(i, j-k):
                    lo = k+1
                else:
                    hi = k
                    
            return 1 + dp(i-1, lo-1)
                    
        return dp(K, N)


from functools import lru_cache


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k: int, n: int) -> int:
            # k == 0 is invalid but not 'impossible'/infinity. Value 0 ensures formula correctness.
            # dp[k][n] = min{1 + max(dp[k-1][i], dp[k][n-i]) for i in [1, n]}
            # dp[0][:]
            if k <= 0:
                return 1 << 31
            if k == 1:
                return n
            if n <= 0:
                return 0
            # Following line is required; o.w. result is not right.
            # When picking 1st floor to drop egg, if it breaks, no more dropping is needed so dp[:][0] == 0
            if n <= 1:
                return n
            # Find the first floor where value starts to increase.
            left, right = 1, n
            while left <= right:
                mid = (left + right) // 2
                if dp(k - 1, mid - 1) >= dp(k, n - mid):
                    right = mid - 1
                else:
                    left = mid + 1
            # Compare points.
            return 1 + dp(k - 1, left - 1)

        return dp(K, N)

from functools import lru_cache


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k: int, n: int) -> int:
            if k <= 0:
                return 0
            if k == 1:
                return n
            # Following line is required; o.w. result is not right.
            if n <= 1:
                return n
            # Find the first floor where dp(k - 1, i - 1) >= dp(k, n - i)
            # such point must exist because dp(k, n-i) has min as dp(k, 0) == 0
            left, right = 1, n
            while left <= right:
                mid = (left + right) // 2
                if dp(k - 1, mid - 1) >= dp(k, n - mid):
                    right = mid - 1
                else:
                    left = mid + 1
            return 1 + dp(k - 1, left - 1)

        return dp(K, N)


from functools import lru_cache

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # time complexity: O(K*N*logN)
        # space complexity: O(K*N)
        @lru_cache(None)
        def dp(k, n): # k eggs, n floors
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            l, r = 1, n + 1
            while l < r:
                m = l + (r - l) // 2
                if dp(k-1, m-1) >= dp(k, n-m):
                    r = m
                else:
                    l = m + 1
            return 1 + max(dp(k-1, l-1), dp(k, n-l))
        
        return dp(K, N)

class Solution:
    def binary_search(self,A,k,n):
        lo = 0
        hi = n
        mid = (lo+hi)//2
        while lo<hi:
            if A[k-1][mid-1]==A[k][n-mid]:
                return mid
            if A[k-1][mid-1]>A[k][n-mid]:
                hi = mid
            else:
                lo = mid+1
            mid = (lo+hi)//2
            
        return lo
    def superEggDrop(self, K: int, N: int) -> int:
        if N==1:
            return 1
        # k=0
        # n=N
        # while n>0:
        #     k+=1
        #     n//=2
        # if K>k:
        #     return k
        A = [[0 for n in range(N+1)] for k in range(K+1)]
        
        for n in range(N+1):
            A[1][n] = n
        for k in range(K+1):
            A[k][1] = 1
            A[k][2] = 2
        
        for k in range(2,K+1):
            low=1
            for n in range(3,N+1):
                # linear search
                # m=1
                # while A[k-1][m-1]<A[k][n-m]:
                #     m+=1
                
                #binary search
                # m = self.binary_search(A,k,n)
                # A[k][n] = 1+max(A[k-1][m-1],A[k][n-m])
                
                # tip-toe
                # print('k =',k,' n = ',n,low,'    ', A[k-1][low],'   ',A[k][n-low-1],'   ',A[k][n])
                if A[k-1][low]<A[k][n-low-1]:
                    low+=1
                  
                A[k][n] = 1+A[k-1][low]
                # print('k =',k,' n = ',n,low,'    ', A[k-1][low],'   ',A[k][n-low-1],'   ',A[k][n])
                # print('')
        return A[-1][-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if n == 0:
                ans = 0
            elif k == 1:
                ans = n
            else:
                lo, hi = 1, n
                # keep a gap of 2 X values to manually check later
                while lo < hi:
                    x = (lo + hi) // 2
                    t1 = dp(k-1, x-1)
                    t2 = dp(k, n-x)

                    if t1 < t2:
                        lo = x + 1
                    else:
                        hi = x
                ans = 1 + max(dp(k-1, lo-1), dp(k, n-lo))
            return ans
        return dp(K,N)


class Solution:
    def binary_search(self,A,k,n):
        lo = 0
        hi = n
        mid = (lo+hi)//2
        while lo<hi:
            if A[k-1][mid-1]==A[k][n-mid]:
                return mid
            if A[k-1][mid-1]>A[k][n-mid]:
                hi = mid
            else:
                lo = mid+1
            mid = (lo+hi)//2
            
        return lo
    def superEggDrop(self, K: int, N: int) -> int:
        if N==1:
            return 1
        if K==1:
            return N
        A = [n+1 for n in range(N)]
        At = [1 for n in range(N)]
        for k in range(1,K):
            i=0
            while At[i]<N:
                i+=1
                At[i] = At[i-1] + A[i-1]+1
            if k<K-1:
                At,A=A,At
        return i+1
#         k=0
#         n=N
#         while n>0:
#             k+=1
#             n//=2
#         if K>k:
#             return k
#         A = [[0 for n in range(N+1)] for k in range(K+1)]
        
#         for n in range(N+1):
#             A[1][n] = n
#         for k in range(K+1):
#             A[k][1] = 1
#             A[k][2] = 2
#         for k in range(2,K+1):
#             low=1
#             for n in range(3,N+1):
#                 # linear search
#                 # m=1
#                 # while A[k-1][m-1]<A[k][n-m]:
#                 #     m+=1
                
#                 #binary search
#                 # m = self.binary_search(A,k,n)
#                 # A[k][n] = 1+max(A[k-1][m-1],A[k][n-m])
                
#                 # tip-toe
#                 if A[k-1][low]<A[k][n-low-1]:
#                     low+=1
                  
#                 A[k][n] = 1+A[k-1][low]
        return A[-1][-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        memo={}
        
        def dp(k,n):
            if (k,n) not in memo:
                if n==0:
                    ans=0
                elif k==1:
                    ans=n
                else:
                    lo,hi=1,n
                    while lo+1<hi:
                        x=(lo+hi)//2
                        t1=dp(k-1,x-1)
                        t2=dp(k,n-x)
                        
                        if t1<t2:
                            lo=x
                        elif t1>t2:
                            hi=x
                        else:
                            lo=hi=x
                    
                    ans=1+min(max(dp(k-1,x-1),dp(k,n-x)) for x in (lo,hi))
                
                memo[k,n]=ans
            return memo[k,n]
        
        return dp(K,N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[i for i in range(N+1)]]
        for i in range(K-1):
            dp.append( [0] * (N+1))
            
        for i in range(1, K):
            k = 1
            for j in range(1, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[-1][-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        mem = [[None for _ in range(N)] for _ in range(K - 1)]
        def dp(k, n, mem):
            if n <= 1 or k == 1:
                return n
            if mem[k-2][n-1] is None:
                l, r = 1, n
                while l + 1 < r:
                    i = (l + r) // 2
                    if dp(k - 1, i - 1, mem) < dp(k, n - i, mem):
                        l = i
                    elif dp(k - 1, i - 1, mem) > dp(k, n - i, mem):
                        r = i
                    else:
                        l = r = i
                mem[k-2][n-1] = min(max(dp(k - 1, l - 1, mem), dp(k, n - l, mem)), max(dp(k - 1, r - 1, mem), dp(k, n - r, mem))) + 1
            return mem[k-2][n-1]
        return dp(K, N, mem)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        self.memo = {}

        return self.cal_eggs(K, N)

    def find_that_floor(self,K,N):
        left, right = 1, N
        while (left <= right):
            mid = (left + right) // 2
            # if it breaks;
            r1 = 1 + self.cal_eggs(K - 1, mid - 1)
            # if it not breaks;
            r2 = 1 + self.cal_eggs(K, N - mid)

            if r1 == r2:
                return mid
            elif r1 < r2:
                left = mid + 1
            else:
                right = mid - 1

        return right

    def cal_eggs(self, K, N):
        # print(K,N)
        if N == 0: return 0
        if K == 1: return N

        if (K, N) not in self.memo:
            r = 2 ** 32 - 1
            now_floor = self.find_that_floor(K,N)
            for floor in range(now_floor, min(now_floor + 2,N+1)):
                # if it breaks;
                r1 = 1 + self.cal_eggs(K - 1, floor - 1)
                # if it not breaks;
                r2 = 1 + self.cal_eggs(K, N - floor)

                r = min(r, max(r1, r2))

            self.memo[(K, N)] = r

        return self.memo[(K, N)]


class Solution:
    def binary_search(self,A,k,n):
        lo = 0
        hi = n
        mid = (lo+hi)//2
        while lo<hi:
            if A[k-1][mid-1]==A[k][n-mid]:
                return mid
            if A[k-1][mid-1]>A[k][n-mid]:
                hi = mid
            else:
                lo = mid+1
            mid = (lo+hi)//2
            
        return lo
    def superEggDrop(self, K: int, N: int) -> int:
        # if N==1:
        #     return 1
        if K==1:
            return N
        A = [n+1 for n in range(N)]
        At = [1 for n in range(N)]
        for k in range(1,K):
            i=0
            while At[i]<N:
                i+=1
                At[i] = At[i-1] + A[i-1]+1
            if k<K-1:
                At,A=A,At
        return i+1
#         k=0
#         n=N
#         while n>0:
#             k+=1
#             n//=2
#         if K>k:
#             return k
#         A = [[0 for n in range(N+1)] for k in range(K+1)]
        
#         for n in range(N+1):
#             A[1][n] = n
#         for k in range(K+1):
#             A[k][1] = 1
#             A[k][2] = 2
#         for k in range(2,K+1):
#             low=1
#             for n in range(3,N+1):
#                 # linear search
#                 # m=1
#                 # while A[k-1][m-1]<A[k][n-m]:
#                 #     m+=1
                
#                 #binary search
#                 # m = self.binary_search(A,k,n)
#                 # A[k][n] = 1+max(A[k-1][m-1],A[k][n-m])
                
#                 # tip-toe
#                 if A[k-1][low]<A[k][n-low-1]:
#                     low+=1
                  
#                 A[k][n] = 1+A[k-1][low]
        return A[-1][-1]

class Solution(object):
    def superEggDrop(self, K, N):
        dp=[[float('inf')]*(N+1) for _ in range(K+1)]
        for i in range(1, K+1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N+1):
            dp[1][j] = j
            
        for i in range(2, K+1):
            k = 1
            for j in range(2, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[K][N]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[i for i in range(N+1)]]

        for _ in range(K-1):
            dp.append([0, 1] + [0] * (N-1))
        
        for i in range(1, K):
            k = 1
            for j in range(2, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[-1][-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('Inf')] * (N + 1) for _ in range(K + 1)]
        
        for i in range(1, K + 1):
            dp[i][0], dp[i][1] = 0, 1
            
        for j in range(1, N + 1):
            dp[1][j] = j
            
        for i in range(2, K + 1):
            k = 1
            for j in range(2, N + 1):
                while k < j + 1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
                    
        return dp[K][N]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp=[[float('inf')]*(N+1) for _ in range(K+1)]
        for i in range(1, K+1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N+1):
            dp[1][j] = j
            
        for i in range(2, K+1):
            k = 1
            for j in range(2, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[K][N]



import math
from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            if k >= math.log(n, 2): return int(math.log(n, 2))+1
            ans = sys.maxsize
            l, r = 1, n + 1
            while l < r:
                m = l + (r - l) //2
                if dp(k-1, m-1) >= dp(k, n-m):
                    r = m
                else:
                    l = m + 1
            ans = min(ans, 1 + max(dp(k-1, l-1), dp(k, n-l)))
            return ans
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        res = [[0]*(N+1) for _ in range(K)]
        # 初始化第一行
        for i in range(N+1):
            res[0][i] = i;
        # 从第二行开始
        if K == 1:
            return N
        for k in range(1,K):
            j = 1
            for i in range(1, N+1):
                while j < i+1 and res[k-1][j-1] < res[k][i-j]:
                    j += 1
                res[k][i] = 1 + res[k-1][j-1]
                # for j in range(1,i+1):
                #     if res[k-1][j-1] == res[k][i-j]:
                #         res[k][i] = 1 + res[k-1][j-1]
                #     else:
                #         continue
        # print(res) 
        return int(res[K-1][N])


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('inf')] * (N+1) for _ in range(K+1)]
        for k in range(1, K+1):
            dp[k][1] = 1
            dp[k][0] = 0
        for n in range(1, N+1):
            dp[1][n] = n
        
        for k in range(2, K+1):
            x = 1
            for n in range(2, N+1):
                while x < n+1 and dp[k][n-x] > dp[k-1][x-1]:
                    x += 1
                dp[k][n] = 1 + dp[k-1][x-1]
        #print(dp)
        return dp[-1][-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if n == 0:
                ans = 0
            elif k == 1:
                ans = n
            else:
                lo, hi = 1, n
                # keep a gap of 2 X values to manually check later
                while lo < hi:
                    x = (lo + hi) // 2
                    t1 = dp(k-1, x-1)
                    t2 = dp(k, n-x)

                    if t1 < t2:
                        lo = x + 1
                    else:
                        hi = x
                ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                              for x in (lo, hi))
            return ans
        return dp(K,N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        @lru_cache(None)
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x + 1
                        else:
                            hi = x

                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                                  for x in (lo, hi))

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    l, r = 1, n
                    while l + 1 < r:
                        x = (l + r)//2
                        t1 = dp(k - 1, x - 1)
                        t2 = dp(k, n - x)
                        if t1 < t2:
                            l = x
                        elif t1 > t2:
                            r = x
                        else:
                             l = r = x
                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                                  for x in (l, r))
                memo[(k, n)] = ans
            return memo[(k, n)]
        return dp(k, n)
             


from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            ans = sys.maxsize
            l, r = 1, n + 1
            while l < r:
                m = l + (r - l) //2
                if dp(k-1, m-1) >= dp(k, n-m):
                    r = m
                else:
                    l = m + 1
            ans = min(ans, 1 + max(dp(k-1, l-1), dp(k, n-l)))
            return ans
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # special case for K = 1
        if K == 1:
            return N
        
        # initialize data
        Rp = [i for i in range(0, N+1)]
        R = [0] * (N+1)
        R[1] = 1
        
        k = 2
        while k <= K:
            l1 = 0
            for n in range(2, N+1):
                #if n < 2**k:
                #    R[n] = n.bit_length() 
                if Rp[n-l1-1] >= R[n-1]:
                    R[n] = R[n-1] + 1
                else:
                    R[n] = R[n-1]
                
                if R[n] > R[n-1]:
                    l1 = n-1
             
            Rp, R = R, Rp
            k += 1
            
        return Rp[N]
                
            


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp = [[0 for _ in range(N+1)] for _ in range(K+1)]

        dp[1] = list(range(N+1))
        for i in range(2, K+1):
            k = 1
            for j in range(1, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
                # if i > j:
                #     dp[i][j] = dp[i-1][j]
                # else:
                #     val = N + 1
                #     for k in range(1, j+1):
                #         val = min(val, 1 + max(dp[i-1][k-1], dp[i][j-k]))
                #     dp[i][j] = val
        # print(dp)
        return dp[-1][-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # we have floors = dp[nummoves][eggs]
        dp = [[
              0
              for egg in range(K+1)] 
              for moves in range(305)]
        print(N)
         
        for move in range(1, 300):
            for eggs in range(1, K+1):
                dp[move][eggs] = 1 + dp[move-1][eggs-1] + dp[move-1][eggs]
                if dp[move][eggs]>=N:
                    return move


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        if N == 1:
            return 1
        
        eggSolutions = [[None for n in range(N+1)] for k in range(K+1)]        
        for n in range(1, N+1):
            eggSolutions[1][n] = n
        for k in range(1, K+1):
            eggSolutions[k][1] = 1
            eggSolutions[k][2] = 2
        
        nextPVals = [i for i in range(N+1)]
        for k in range(2, K+1):
            pVals = nextPVals
            nextPVals = [None, None, 2]
            pIndex = 2
            for n in range(3, N+1):
                p = pVals[pIndex]
                minDrops = 1 + max(eggSolutions[k-1][p-1], eggSolutions[k][n-p])
                eggSolutions[k][n] = minDrops
                if eggSolutions[k][n] > eggSolutions[k][n-1]:
                    pIndex += 1
                    nextPVals.append(n)
        
        return eggSolutions[K][N]

class Solution(object):
    def superEggDrop(self, K, N):
        dp = range(N+1)
        for i in range(2, K+1):
            k = 1
            ndp = [0, 1] + [float('inf')]*(N-1)
            for j in range(2, N+1):
                while k < j+1 and ndp[j-k] > dp[k-1]:
                    k += 1
                ndp[j] = 1 + dp[k-1]
            dp = ndp
        return dp[N]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        self.memo = {}

        return self.cal_eggs(K, N)

    def find_that_floor(self,K,N):
        left, right = 1, N
        while (left <= right):
            mid = (left + right) // 2
            # if it breaks;
            r1 = 1 + self.cal_eggs(K - 1, mid - 1)
            # if it not breaks;
            r2 = 1 + self.cal_eggs(K, N - mid)

            if r1 == r2:
                return mid
            elif r1 < r2:
                left = mid + 1
            else:
                right = mid - 1

        return right

    def cal_eggs(self, K, N):
        # print(K,N)
        if N == 0: return 0
        if K == 1: return N

        if (K, N) in self.memo:
            pass
        else:
            r = 2 ** 32 - 1
            now_floor = self.find_that_floor(K,N)
            for floor in range(now_floor, min(now_floor + 2,N+1)):
                # if it breaks;
                r1 = 1 + self.cal_eggs(K - 1, floor - 1)
                # if it not breaks;
                r2 = 1 + self.cal_eggs(K, N - floor)

                r = min(r, max(r1, r2))

            self.memo[(K, N)] = r

        return self.memo[(K, N)]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        @lru_cache(None)
        def dp(k, n):
            if n == 0: return 0
            if k == 1: return n
            
            res = float('inf')
            
            lo = 1
            hi = n
            
            while lo <= hi:
                mid = (lo + hi) // 2
                
                broken = dp(k - 1, mid - 1)
                no_broken = dp(k, n - mid)
                
                if broken > no_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, no_broken + 1)
            return res
        
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [i for i in range(N+1)]
        for j in range(1, K):
            prev = dp.copy()
            m = 1
            for i in range(2, N+1):
                while m < i and dp[i-m] >= prev[m-1] and dp[i-m-1] >= prev[m]:
                    m += 1
                dp[i] = max(dp[i-m], prev[m-1]) + 1
        return dp[N]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (N + 1) for _ in range(K + 1)]
        for n in range(1, N + 1):
            dp[1][n] = n
        for k in range(2, K + 1):
            dp[k][1] = 1
        # dp[k][n] <= n
        for k in range(2, K + 1):
            m = 1
            for n in range(2, N + 1):
                while m < n and dp[k - 1][m - 1] < dp[k][n - m]:
                    m += 1
                # dp[k][n] = min(max(dp[k - 1][m - 1], dp[k][n - m]) + 1 for m in range(1, n + 1))
                # l, r = 1, n
                # while l < r:
                #     m = (l + r) >> 1
                #     a, b = dp[k - 1][m - 1], dp[k][n - m]
                #     if a > b:
                #         r = m
                #     elif b > a:
                #         l = m + 1
                #     else:
                #         break
                dp[k][n] = max(dp[k - 1][m - 1], dp[k][n - m]) + 1
        # for _ in dp:
        #     print(_)
        return dp[-1][-1]

from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # return self.bottomUp(K, N)
        return self.findMoves(K, N)
    
    @lru_cache(maxsize = None)
    def findMoves(self, K, N):
        if K == 1 or N<=1:
            return N
        f = N
        
        left, right = 1, N
        while (left < right):
            mid = (left + right) // 2
            
            broken = self.findMoves(K-1, mid-1)
            intact = self.findMoves(K, N-mid)
            if broken > intact:
                right = mid
            else:
                left = mid+1
        
        mid = left -1
        return 1 + max(self.findMoves(K-1, mid-1), self.findMoves(K, N-mid))
#         intact = 
            
#         for x in range (1, N+1):
#             f = min(1 + max(self.findMoves(K-1, x-1), self.findMoves(K, N-x)), f)
#         return f
    
    def bottomUp(self, K, N):
        dp = [[i for i in range(N+1)] for _ in range(K+1)]
        for i in range(2, K+1):
            for j in range(1, N+1):
                min_drops = N
                for k in range(1, j+1):
                    min_drops = min(min_drops, 1 + max(dp[i-1][k-1], dp[i][j-k]))
                dp[i][j] = min_drops
        return dp[K][N]

import numpy as np


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        drops = 0                           # the number of eggs dropped
        floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

        while floors[K] < N:                # until we can reach N floors with K eggs 

            for eggs in range(K, 0, -1):
                floors[eggs] += 1 + floors[eggs - 1]
            drops += 1

        return drops
    
    
    
    


class Solution:
    def superEggDrop1(self, K: int, N: int) -> int: # 超时！！！
        memo = [[2**31-1] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            
            if memo[k][n] < 2**31-1:
                return memo[k][n]
            
            ans = memo[k][n]
            for i in range(1, n+1):
                ans = min(ans, 1+max(dp(k-1, i-1), dp(k, n-i)))
                # 极小极大过程！！！alike
            memo[k][n] = ans
            return ans
        return dp(K, N)
    
    # D(K-1, i-1), monotonically increasing with i
    # D(K, N-i) is monotonically decreasing with i!
    
    # binary search!
    # D(K, N) = 1 + min(max(D(K-1, i-1), D(K, N-i))), 1<=i<=N
    # f(i) = D(K-1, i-1), f(i) is monotonically increasing with i
    # g(i) = D(K, N-i), g(i) is monotonically decreasing with i
    
    # we can use binary search to find i that minimizes max(f(i), g(i))
    #
    # 一个函数单调增；一个函数单调减
    # min (max (f, g))
    # 就可以使用binary search
    # f(i) < g(i) 的时候，说明i太小了，需要增大i
    # f(i) > g(i) 的时候，说明i太大了，需要减少i
    # 我们需要的是first i, such that f(i) >= g(i)
    # time complexity = O(KNlogN) smaller than O(K*N*N)
    # space is same O(KN)
    
    def superEggDrop(self, K: int, N: int) -> int: # 超时！！！
        memo = [[2**31-1] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            
            if memo[k][n] < 2**31-1:
                return memo[k][n]
            
            #ans = memo[k][n]
            #for i in range(1, n+1):
            #    ans = min(ans, 1+max(dp(k-1, i-1), dp(k, n-i)))
                # 极小极大过程！！！alike
            left = 1
            right = n + 1
            while left < right:
                mid = left + (right - left) // 2
                if dp(k-1, mid-1) >= dp(k, n-mid):
                    right = mid
                else:
                    left = mid + 1
            
            memo[k][n] = 1 + max(dp(k-1, left-1), dp(k, n-left))
            return memo[k][n]
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp=[[float('inf')]*(N+1) for _ in range(K+1)]
        for i in range(1, K+1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N+1):
            dp[1][j] = j
            
        for i in range(2, K+1):
            k = 1
            for j in range(2, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[K][N]
        
#     def superEggDrop(self, K: int, N: int) -> int:
#         dp = [[float('inf') for _ in range(N + 1)] for _ in range(K + 1)]
#         for i in range(1, K + 1):
#             dp[i][0] = 0
#             dp[i][1] = 1
#         for j in range(1, N + 1):
#             dp[1][j] = j
        
#         for i in range(2, K + 1):
#             for j in range(2, N + 1):
#                 for k in range(1, j + 1):
#                     dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][k - 1], dp[i][j - k]))
#         return dp[-1][-1]


from math import comb


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp={}
        for i in range(N+1):
            dp[(i,0)] = 0
        for k in range(1,K+1):
            dp[(1,k)] = 1
        for k in range(1,K+1):
            for n in range(2,N+1):
                dp[(n,k)] = 1 + dp[(n-1),k] + dp[(n-1),k-1]
        num = 1
        while dp[(num,K)]<N:
            num+=1
        return num



class Solution:
    def superEggDrop(self, eggs: int, floors: int) -> int:
        
        dp = [[-1 for _ in range(floors+1)] for _ in range(eggs+1)]
        
#         int dp(int k, int n) {
#             if (k <= 0) return 0;
#             if (k == 1) return n;
#             if (n <= 1) return n;
#             if (m_[k][n] != INT_MIN) return m_[k][n];

#             // broken[i]   = dp(k - 1, i - 1) is incresing with i.
#             // unbroken[i] = dp(k,     n - i) is decresing with i.
#             // dp[k][n] = 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n
#             // find the smallest i such that broken[i] >= unbroken[i],
#             // which minimizes max(broken[i], unbroken[i]).
#             int l = 1;
#             int r = n + 1;
#             while (l < r) {
#               int m = l + (r - l) / 2;
#               int broken = dp(k - 1, m - 1);
#               int unbroken = dp(k, n - m);
#               if (broken >= unbroken)
#                 r = m;
#               else
#                 l = m + 1;
#             }
        
        def search(eggs, floors):
            if eggs <= 0:
                return 0
            elif eggs == 1:
                return floors
            elif floors <= 1:
                return floors
            elif dp[eggs][floors] != -1:
                return dp[eggs][floors]
            
            l, r = 1, floors+1
            while l < r:
                mid = l + (r-l) // 2
                broken = search(eggs-1, mid-1)
                intact = search(eggs, floors-mid)
                if broken < intact:
                    l = mid + 1
                else:
                    r = mid
            
            dp[eggs][floors] = 1 + search(eggs-1, l-1)
            return dp[eggs][floors]
        
        return search(eggs, floors)

class Solution:
    #https://leetcode.com/problems/super-egg-drop/discuss/159079/Python-DP-from-kn2-to-knlogn-to-kn
    def superEggDrop(self, K: int, N: int) -> int:
        dp=[[float('inf')]*(N+1) for _ in range(K+1)]
        for i in range(1, K+1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N+1):
            dp[1][j] = j
            
        for i in range(2, K+1):
            k = 1
            for j in range(2, N+1):
                while k < j+1 and dp[i][j-k] > dp[i-1][k-1]:
                    k += 1
                dp[i][j] = 1 + dp[i-1][k-1]
        return dp[K][N]
        
#     def superEggDrop(self, K: int, N: int) -> int:
#         dp = [[float('inf') for _ in range(N + 1)] for _ in range(K + 1)]
#         for i in range(1, K + 1):
#             dp[i][0] = 0
#             dp[i][1] = 1
#         for j in range(1, N + 1):
#             dp[1][j] = j
        
#         for i in range(2, K + 1):
#             for j in range(2, N + 1):
#                 for k in range(1, j + 1):
#                     dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][k - 1], dp[i][j - k]))
#         return dp[-1][-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = [[-1]*(K+1) for _ in range(N+1)]
        @lru_cache(None)
        def drop(egg, floor):
            if egg==1 or floor<=1:
                return floor
            if memo[floor][egg]!=-1:
                return memo[floor][egg]
            minAttempts = float('inf')
            l=1;h=floor
            while l<=h:
                mid = (l+h)//2
                low = drop(egg-1, mid-1)
                high = drop(egg, floor-mid)
                attempts = 1 + max(low, high)
                if low<high:
                    l=mid+1
                else:
                    h=mid-1
                minAttempts = min(minAttempts, attempts)
            memo[floor][egg] = minAttempts
            return minAttempts
        return drop(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def DP(k, n):
            if (k, n) not in memo:
                if n == 0:
                    res = 0
                elif k == 1:
                    res = n
                else:
                    l, r = 1, n
                    while l < r:
                        mid = (l + r) // 2
                        t1 = DP(k-1, mid-1)
                        t2 = DP(k, n-mid)
                        
                        if t1 < t2:
                            l = mid + 1
                        else:
                            r = mid
                    
                    res = 1 + max(DP(k-1, l-1), DP(k, n-l))
                memo[k, n] = res
            return memo[k, n]
        
        return DP(K, N)

class Solution:
    def superEggDrop1(self, K: int, N: int) -> int: # 超时！！！
        memo = [[2**31-1] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            
            if memo[k][n] < 2**31-1:
                return memo[k][n]
            
            ans = memo[k][n]
            for i in range(1, n+1):
                ans = min(ans, 1+max(dp(k-1, i-1), dp(k, n-i)))
                # 极小极大过程！！！alike
            memo[k][n] = ans
            return ans
        return dp(K, N)
    
    # D(K-1, i-1), monotonically increasing with i
    # D(K, N-i) is monotonically decreasing with i!
    
    # binary search!
    # D(K, N) = 1 + min(max(D(K-1, i-1), D(K, N-i))), 1<=i<=N
    # f(i) = D(K-1, i-1), f(i) is monotonically increasing with i
    # g(i) = D(K, N-i), g(i) is monotonically decreasing with i
    
    # we can use binary search to find i that minimizes max(f(i), g(i))
    #
    # 一个函数单调增；一个函数单调减
    # min (max (f, g))
    # 就可以使用binary search
    # f(i) < g(i) 的时候，说明i太小了，需要增大i
    # f(i) > g(i) 的时候，说明i太大了，需要减少i
    # 我们需要的是first i, such that f(i) >= g(i)
    # time complexity = O(KNlogN) smaller than O(K*N*N)
    # space is same O(KN)
    
    def superEggDrop3(self, K: int, N: int) -> int: # 使用binary search，可以得到最好的结果了！
        memo = [[2**31-1] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            
            if memo[k][n] < 2**31-1:
                return memo[k][n]
            
            #ans = memo[k][n]
            #for i in range(1, n+1):
            #    ans = min(ans, 1+max(dp(k-1, i-1), dp(k, n-i)))
                # 极小极大过程！！！alike
            left = 1
            right = n + 1
            res = 2**31-1
            while left < right:
                mid = left + (right - left) // 2
                broken = dp(k-1, mid-1)
                notbroken = dp(k, n-mid)
                if broken >= notbroken: # f(mid) >= g(mid) 最小的mid!
                    right = mid
                    res = min(res, broken+1)
                else:
                    left = mid + 1
                    res = min(res, notbroken+1)
            
            memo[k][n] = res #1 + max(dp(k-1, left-1), dp(k, n-left))
            return memo[k][n]
        return dp(K, N)
    
    def superEggDrop(self, K, N):
        amax = 2**31-1
        memo = [[amax] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n # this time k>1
            
            if memo[k][n] != amax:
                return memo[k][n]
            left = 1
            right = n + 1
            while left < right:
                mid = left + (right - left)//2
                broken = dp(k-1, mid-1)
                notbroken = dp(k, n-mid) # mid+1 to N
                if broken >= notbroken:
                    right = mid
                else:
                    left = mid + 1
            ans = 1 + max(dp(k-1, left-1), dp(k, n-left))
            memo[k][n] = ans
            return ans
        return dp(K, N)
    
    def superEggDrop2(self, K: int, N: int) -> int: # 使用binary search，很好了！
        memo = [[2**31-1] * (N+1) for _ in range(K+1)]
        
        def dp(k, n):
            if k == 0: return 0
            if k == 1: return n
            if n <= 1: return n
            
            if memo[k][n] < 2**31-1:
                return memo[k][n]
            
            #ans = memo[k][n]
            #for i in range(1, n+1):
            #    ans = min(ans, 1+max(dp(k-1, i-1), dp(k, n-i)))
                # 极小极大过程！！！alike
            left = 1
            right = n + 1
            while left < right:
                mid = left + (right - left) // 2
                # broken >= not_broken
                if dp(k-1, mid-1) >= dp(k, n-mid): # f(mid) >= g(mid) 最小的mid!
                    right = mid
                else:
                    left = mid + 1
            # 通过binary search找到left是核心！找极值点！
            memo[k][n] = 1 + max(dp(k-1, left-1), dp(k, n-left))
            return memo[k][n]
        return dp(K, N)
    
    def superEggDrop4(self, K, N):
        def f(x):
            ans = 0
            r = 1
            for i in range(1, K+1):
                r *= x-i+1
                r //= i
                ans += r
                if ans >= N: break
            return ans
        
        # 还是使用了binary search! 速度很快啊！！！
        lo, hi = 1, N
        while lo < hi:
            mi = (lo + hi) // 2
            if f(mi) < N:
                lo = mi + 1
            else:
                hi = mi
        return lo


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (K + 1) for i in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: return m
        return search(N, K)
            
                


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(k, n):
            # base case
            if k == 1:
                return n
            if n == 0:
                return 0

            if (k, n) in memo:
                return memo[(k, n)]

            res = float('inf')
            # for i in range(1, n + 1):
            #     res = min(res, max(dp(k, n - i), dp(k - 1, i - 1)) + 1)
            # binary search
            res = float('inf')
            lo, hi = 1, n
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                broken = dp(k - 1, mid - 1)
                not_broken = dp(k, n - mid)
                if not_broken > broken:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
                else:
                    hi = mid - 1
                    res = min(res, broken + 1)
            memo[(k, n)] = res
            return res
        return dp(K, N)


class Solution:
    def superEggDrop(self, e: int, f: int) -> int:
        
        self.cache = [[-1]*(f+1) for _ in range(e+1)]
        
        return self.drop(e,f)
    
    def drop(self,e,f):
        
        if f == 0 or f == 1:
            return f
        
        if e == 1:
            return f
        
        if self.cache[e][f] != -1:
            return self.cache[e][f]
        
        ans = float('inf')
        
        l = 1
        h = f
        
        while l <= h:
            
            mid = (l+h)//2
            
            low = 0
            high = 0
            
            if self.cache[e-1][mid-1] != -1:
                low = self.cache[e-1][mid-1]
            else:
                low = self.drop(e-1,mid-1)
            
            if self.cache[e][f-mid] != -1:
                high = self.cache[e][f-mid]
            else:
                high = self.drop(e,f-mid)
            
            if low < high:
                
                l = mid + 1
                
            else:
                
                h = mid -1
            ans = min(max(low,high)+1,ans)
            
        
#         for k in range(1,f+1):
            
#             low = 0
#             high = 0
            
#             if self.cache[e-1][k-1] != -1:
#                 low = self.cache[e-1][k-1]
#             else:
#                 low = self.drop(e-1,k-1)
            
#             if self.cache[e][f-k] != -1:
#                 high = self.cache[e][f-k]
#             else:
#                 high = self.drop(e,f-k)
            
#             ans = min(max(low,high)+1,ans)
            
        self.cache[e][f] = ans
            
        return ans


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dfs(k, n):
            if k == 1:
                # Only one egg, start from floor.
                return n
            if n <= 1:
                return n
            if (k, n) in memo:
                return memo[(k, n)]
            
            l, r = 0, n
            
            while l < r:
                mid = l + (r - l) // 2
                left_cnt = dfs(k-1, mid-1)
                right_cnt = dfs(k, n-mid)
                if left_cnt < right_cnt:
                    l = mid + 1
                else:
                    r = mid
            
            memo[(k, n)] = 1 + max(dfs(k-1, l-1), dfs(k, n-l))
            return memo[(k, n)]
        
        return dfs(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # https://leetcode.com/problems/super-egg-drop/discuss/443089/Simplest-Python-DP-Solution-with-Detailed-Explanation-99Time-100Mem
        # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
        # M = 300 # big enough number
        # dp = [[0 for j in range(K+1)] for i in range(M+1)]
        # # Initialization 1 --> no move no floor --> dp[0][*] = 0
        # # Initialization 2 --> no egg no floor --> dp[*][0] = 0
        # # General case --> we want to find dp[m][k] --> we pick one egg and drop (1 move)
        # #              --> now we have k or k-1 eggs, depending on whether the previous egg is broken
        # #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
        # for i in range(1, M+1):
        #     for j in range(1, K+1):
        #         dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
        #         if dp[i][j] >= N:
        #             return i
        memo = dict()    
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in memo:
                return memo[(K, N)]
            # res = float('inf')
            low, high = 1, N + 1
            while low < high:
                mid = (low + high)//2
                broken = dp(K-1, mid -1)
                notBroken = dp(K, N-mid)
                if broken >= notBroken:
                    high = mid
                    # res = min(broken + 1, res)
                else:
                    low = mid + 1
                    # res = min(notBroken + 1, res)
            memo[(K,N)] = 1 + max(dp(K-1, low -1), dp(K, N-low))
            return memo[(K,N)]
        return dp(K, N)
            
                
            


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        
        def dp(k, n):
            if k <= 0: return 0
            if k == 1: return n
            if n <= 1: return n
            if (k,n) in memo:
                return memo[(k,n)]
            l, r = 1, n+1
            while l < r:
                mid = l + (r-l) //2
                broken = dp(k - 1, mid - 1)
                unbroken = dp(k, n - mid)
                if broken >= unbroken:
                    r = mid
                else:
                    l = mid + 1
            memo[(k,n)] = 1 + dp(k - 1, l - 1)
            return memo[(k,n)]
           
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dfs(k, n):
            if k == 1:
                return n
            if n <= 1:
                return n
            if (k, n) in memo:
                return memo[(k, n)]
            
            l, r = 0, n
            while l < r:
                mid = l + (r - l) // 2
                left_num, right_num = dfs(k-1, mid-1), dfs(k, n-mid)
                if right_num > left_num:
                    l = mid + 1
                else:
                    r = mid
            memo[(k, n)] = 1 + max(dfs(k-1, l-1), dfs(k, n-l))
            return memo[(k, n)]
        
        memo = {}
        return dfs(K, N)


# More specifically, to get the k that best fits each drop, we don't need to go over all floors from 1 to j. 
# As for a fixed k, dp[i][k] goes up as k increases. This means dp[i-1][k-1] will increase and dp[i][j-k] will
# decrease as k goes from 1 to j. The optimal value of k will be the middle point where the two meet. So to 
# get the optimal k value for dp[i][j], we can do a binary search for k from 1 to j.



class Solution(object):
    def superEggDrop(self, K, N):
        def dfs(i, j):
            if i==1:
                return j
            if j==0:
                return 0
            if j==1:
                return 1
            if (i, j) in d:
                return d[i, j]
            lo, hi = 0, j
            while lo < hi:
                mid = (lo+hi)//2
                left, right = dfs(i-1, mid-1), dfs(i, j-mid)
                # print(mid, left, right)
                if left < right:
                    lo = mid + 1
                else:
                    hi = mid
            res = 1 + max(dfs(i-1, lo-1), dfs(i, j-lo))
            d[i, j]=res
            return res
        
        d={}
        return dfs(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        # dp[i] represents dp(1, i)
        dp = range(N + 1)

        for k in range(2, K + 1):
            # dp2 represents dp(k, i)
            dp2 = [0]
            A = 1

            for n in range(1, N + 1):
                costA = max(dp[A - 1], dp2[n - A])
                while A < n:
                    B = A + 1
                    costB = max(dp[B - 1], dp2[n - B])
                    if costB > costA:
                        break
                    costA = costB
                    A += 1
                dp2.append(1 + costA)
            dp = dp2

        return dp[-1]

class Solution:
    
    def eggDrop(self,floors,eggs,m):
        if floors<=1:
            return floors 
        if eggs == 1:
            return floors 
        if (floors,eggs) in m:
            return m[(floors,eggs)]

        l,h = 0,floors
        
        while l<h:
            mid = (l+h)>>1
            kelge,mele = self.eggDrop(mid-1,eggs-1,m) , self.eggDrop(floors-mid,eggs,m)
            if kelge>=mele:
                h = mid
            else:
                l = mid+1
        drops = 1 + max(self.eggDrop(l-1,eggs-1,m),self.eggDrop(floors-l,eggs,m))
        m[(floors,eggs)] = drops
        
        return drops
    def superEggDrop(self, K: int, N: int) -> int:
        
        return self.eggDrop(N,K,{})


class Solution:
    def superEggDrop(self, eggs: int, floors: int) -> int:
        building = [[0] * (eggs+1) for _ in range(floors+1)]
        currFloor = 0
        
        while building[currFloor][eggs] < floors:
            currFloor += 1
            for i in range(1 , eggs+1):
                building[currFloor][i] = building[currFloor-1][i-1] + building[currFloor-1][i] + 1
                
        return currFloor

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        dp = {}
        def num_moves(n, k):
            if (n, k) not in dp:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    left = 1
                    right = n + 1
                    while left < right:
                        floor = (left + right) // 2
                        safe_moves = num_moves(n - floor, k)
                        unsafe_moves = num_moves(floor - 1, k - 1)
                        if safe_moves > unsafe_moves:
                            left = floor + 1
                        else:
                            right = floor

                    floor = left
                    safe_moves = num_moves(n - floor, k)
                    unsafe_moves = num_moves(floor - 1, k - 1)
                    nk_moves = max(safe_moves, unsafe_moves) + 1

                    if floor > 1:
                        prev_floor = left - 1
                        prev_safe_moves = num_moves(n - prev_floor, k)
                        prev_unsafe_moves = num_moves(prev_floor - 1, k - 1)
                        prev_nk_moves = max(prev_safe_moves, prev_unsafe_moves) + 1
                        nk_moves = min(nk_moves, prev_nk_moves)
                    ans = nk_moves
                dp[(n, k)] = ans
            return dp[(n, k)]
        return num_moves(N, K)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = {}
        def num_moves(n, k):
            if (n, k) not in dp:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    left = 1
                    right = n + 1
                    while left < right:
                        floor = (left + right) // 2
                        safe_moves = num_moves(n - floor, k)
                        unsafe_moves = num_moves(floor - 1, k - 1)
                        if safe_moves > unsafe_moves:
                            left = floor + 1
                        else:
                            right = floor

                    floor = left
                    safe_moves = num_moves(n - floor, k)
                    unsafe_moves = num_moves(floor - 1, k - 1)
                    nk_moves = max(safe_moves, unsafe_moves) + 1

                    if floor > 1:
                        prev_floor = left - 1
                        prev_safe_moves = num_moves(n - prev_floor, k)
                        prev_unsafe_moves = num_moves(prev_floor - 1, k - 1)
                        prev_nk_moves = max(prev_safe_moves, prev_unsafe_moves) + 1
                        nk_moves = min(nk_moves, prev_nk_moves)
                    ans = nk_moves
                dp[(n, k)] = ans
            return dp[(n, k)]
        return num_moves(N, K)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        
        def dp(K, N):
            if (K, N) in memo:
                return memo[(K,N)]
            
            if K == 1:
                return N
            if N == 0:
                return 0
            
            res = sys.maxsize
            
            # for i in range(1, N + 1):
            #     res = min(res, max(dp(K - 1, i - 1), dp(K, N - i)) + 1)
            lo, hi = 1, N
            while lo <= hi:
                mid = int(lo + (hi - lo) / 2)
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid)
                
                if broken < not_broken:
                    lo = mid + 1
                    res = min(not_broken + 1, res)
                else:
                    hi = mid - 1
                    res = min(broken + 1, res)
            
            memo[(K, N)] = res
            
            return res
        
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        def dfs(e, f):
            if e == 1:
                return f
            
            if f == 0 or f == 1:
                return f
            
            if (e, f) in cache:
                return cache[(e, f)]
            
            left, right = 1, f + 1
            
            while left < right:
                mid = left + (right - left) // 2
                
                i, j = dfs(e - 1, mid - 1), dfs(e, f - mid)
                
                if i < j:
                    left = mid + 1
                else:
                    right = mid
                
            cache[(e, f)] = 1 + max(dfs(e - 1, left - 1), dfs(e, f - left))
            return cache[(e, f)]
        
        cache = dict()
        return dfs(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        results = [[None for _ in range(N+1)] for _ in range(K+1)]
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            
            if results[K][N]:
                return results[K][N]
            
            
            res = N
            
            left = 1
            right = N
            
            while left <= right:
                mid = int((right+left)/2)
                
                broken_num = dp(K-1, mid-1)
                notbroken_num = dp(K, N-mid)
                if broken_num > notbroken_num:
                    right = mid - 1
                    res = min(res, broken_num + 1)
                else:
                    left = mid + 1
                    res = min(res, notbroken_num + 1)
            
            results[K][N] = res
            # for i in range(1, N+1):
            #     results[K][N] = min(results[K][N], max(dp(K-1, i-1), dp(K, N-i)) + 1)
            
            # return results[K][N]
            return res
        # dp(K, N)
        # print(results)
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = [[-1]*(K+1) for _ in range(N+1)]
        def drop(egg, floor):
            if egg==1 or floor<=1:
                return floor
            if memo[floor][egg]!=-1:
                return memo[floor][egg]
            minAttempts = float('inf')
            l=1;h=floor
            while l<=h:
                mid = (l+h)//2
                low = drop(egg-1, mid-1)
                high = drop(egg, floor-mid)
                attempts = 1 + max(low, high)
                if low<high:
                    l=mid+1
                else:
                    h=mid-1
                minAttempts = min(minAttempts, attempts)
            memo[floor][egg] = minAttempts
            return minAttempts
        return drop(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0]*(N+1) for _ in range(K+1)]
        for i in range(1, N+1):
            dp[1][i] = i
        for i in range(2, K+1):
            s = 1
            for j in range(1, N+1):
                dp[i][j] = j
                while s<j and dp[i][j-s]>dp[i-1][s-1]:
                    s += 1
                dp[i][j] = min(dp[i][j], max(dp[i][j-s], dp[i-1][s-1])+1)


        return dp[K][N]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        num_moves = [n for n in range(N + 1)]

        for k in range(2, K + 1):
            next_num_moves = [0 for _ in range(N + 1)]
            floor = 1
            for n in range(1, N + 1):
                safe_moves = next_num_moves[n - floor]
                unsafe_moves = num_moves[floor - 1]
                nk_moves = 1 + max(safe_moves, unsafe_moves)
                while floor < N:
                    next_floor = floor + 1
                    next_safe_moves = next_num_moves[n - next_floor]
                    next_unsafe_moves = num_moves[next_floor - 1]
                    next_nk_moves = 1 + max(next_safe_moves, next_unsafe_moves)
                    if next_nk_moves < nk_moves:
                        floor = next_floor
                        nk_moves = next_nk_moves
                    else:
                        break
                next_num_moves[n] = nk_moves
            num_moves = next_num_moves
        return num_moves[N]



from math import inf
from typing import List

class Solution:

    def superEggDrop(self, K: int, N: int) -> int:
        self.memo = {}
        return self.rec(K, N)


    def rec(self, i, j):
        if i == 1:
            return j
        if j == 0 or j == 1:
            return j
        if (i, j) in self.memo:
            return self.memo[i, j]
        lo, hi = 0, j
        while lo < hi:
            mid = lo + (hi - lo) // 2
            left, right = self.rec(i - 1, mid - 1), self.rec( i, j - mid)
            if left < right:
                lo = mid + 1
            else:
                hi = mid
        res = 1 + self.max(self.rec(i - 1, lo - 1), self.rec(i, j - lo))
        self.memo[i, j] = res
        return res 
        

    def dp(self, K: int, N: int) -> int:
        #dp[i][j] - i eggs for j floors
        dp = [[inf for _ in range(N + 1)] for _ in range(K + 1)]
        #dp[i][0] -> 0, dp[1][j] -> j, dp[i][1] -> 1
        for i in range(K + 1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(N + 1):
            dp[1][j] = j

        for i in range(2, K + 1):
            for j in range(2, N + 1):
                left, right = 0, j
                while left < right:
                    mid = left + (right - left) // 2
                    if dp[i - 1][mid - 1] < dp[i][j - mid]:
                        left = mid + 1
                    else:
                        right = mid 
                dp[i][j] = 1 + self.max(dp[i - 1][left - 1], dp[i][j - left])
                #for k in range(i, j + 1):
                #    dp[i][j] = self.min(dp[i][j] , 1 + self.max(dp[i - 1][k - 1], dp[i][j - k])
        
        return dp[K][N] 

    def min(self, a, b):
        return a if a < b else b
    def max(self, a, b):
        return a if a > b else b


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        table = dict()
        def dp(K: int, N: int) -> int:
            if (K == 1) : return N
            if (N <= 0) : return 0
            
            if (K, N) in table: return table[(K, N)];
            lo = 1
            hi = N
            while (lo <= hi):
                mid = lo + (hi - lo) // 2
                up = dp(K, N - mid)
                dn = dp(K-1, mid-1)
                if (up >= dn): 
                    lo = mid + 1
                else: 
                    hi = mid - 1
            table[(K, N)] = 1 + min(dp(K, N - hi), dp(K - 1, lo - 1))
            return table[(K, N)]
        return dp(K, N)
        


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = [[0] * (K + 1) for _ in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                memo[m][k] = memo[m - 1][k - 1] + 1 + memo[m - 1][k]
                if memo[m][k] >= N: return m 

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dp(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in memo:
                return memo[(k, n)]
            
            res = sys.maxsize
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(k - 1, mid - 1) 
                safe = dp(k, n - mid) 
                if broken > safe:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, safe + 1)
                    
            memo[(k, n)] = res
            return res
        
        memo = {}
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dp(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in memo:
                return memo[(k, n)]
            
            res = sys.maxsize
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(k - 1, mid - 1) # 碎 
                not_broken = dp(k, n - mid) # 没碎 # res = min(max(碎，没碎) + 1)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
                    
            memo[(k, n)] = res
            return res
        
        memo = {}
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        cache = {}
        def drop(egg, floor):
            if egg==1 or floor<=1:
                return floor
            if (egg, floor) in cache:
                return cache[(egg, floor)]
            minAttempts = float('inf')
            l=1;h=floor
            while l<=h:
                mid = (l+h)//2
                low = drop(egg-1, mid-1)
                high = drop(egg, floor-mid)
                attempts = 1 + max(low, high)
                if low<high:
                    l=mid+1
                else:
                    h=mid-1
                minAttempts = min(minAttempts, attempts)
            cache[(egg, floor)] = minAttempts
            return minAttempts
        return drop(K, N)

class Solution(object):
    def superEggDrop(self, K, N):
        memo = {}
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            if (K, N) in memo:
                return memo[(K, N)]
            res = float('INF')
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            
            memo[(K, N)] = res
            return res

        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        table = dict()
        def dp(K: int, N: int) -> int:
            if (K == 1) : return N
            if (N <= 0) : return 0
            
            if (K, N) in table: return table[(K, N)];
            lo, hi = 1, N
            res = N
            while (lo <= hi):
                mid = lo + (hi - lo) // 2
                up = dp(K, N - mid)
                dn = dp(K-1, mid-1)
                if (up >= dn): 
                    lo = mid + 1
                    res = min(res, 1 + up)
                else: 
                    hi = mid - 1
                    res = min(res, 1 + dn)
            table[(K, N)] = res
            return res
        return dp(K, N)
        


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            
            if (K, N) in memo:
                return memo[(K,N)]
        
            res = float('inf')
            lo, hi = 1, N
            
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K -1, mid - 1)
                not_broken = dp(K, N - mid)
                
                if broken > not_broken:
                    hi = mid -1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            # for i in range(1, N+1):
            #     res = min(res, max(dp(K-1, i -1), dp(K, N - i)) + 1)
            
            memo[(K,N)] = res
            return res
            
        return dp(K, N)
            
        


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # dp[K][N] = min_X(max(dp[K-1][X-1], dp[K][N-X]))
        dp = [[sys.maxsize for i in range(N+1)] for j in range(K+1)]
        
        def DP(k, n):
            if k < 0 or n < 0: return 0
            if k == 0: return 0
            if k == 1: return n
            if n == 0: return 0
            if n == 1: return 1
            
            if dp[k][n] != sys.maxsize:
                return dp[k][n]
            
            # find the minimal dp[k][n]
            l = 0
            r = n
            while (l < r):
                m = (l+r) // 2
                if DP(k-1, m-1) >= DP(k, n-m):
                    r = m
                else:
                    l = m+1
            
            dp[k][n] = 1+max(DP(k-1, l-1), DP(k, n-l))
            return dp[k][n]
        
        return DP(K, N)
            
        
        


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # K=1, moves=N
        # K>=2, moves=max(dfs(K-1, i - 1), dfs(K, N - i))
        
        def dfs(k, n, memo):
            
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in memo:
                return memo[(k, n)]
            
            res = float('inf')
            # for i in range(1, n+1):
            #     res = min(res, max(dfs(k-1, i-1, memo), dfs(k, n-i, memo)) + 1)
            
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dfs(k-1, mid-1, memo)
                no_broken = dfs(k, n-mid, memo)
                if broken > no_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, no_broken + 1)
            memo[(k, n)] = res
            return res
        return dfs(K, N, {})

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x + 1
                        else:
                            hi = x

                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                                  for x in (lo, hi))

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def f(x):
            ans = 0
            r = 1
            for i in range(1, K+1):
                r *= (x-i+1)/i
                #r //= i
                ans += r
                if ans >= N: break
            return ans

        low, high = 1, N
        while low < high:
            middle = (low + high) // 2
            if f(middle) < N:
                low = middle + 1
            else:
                high = middle
        return low


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
#         # brutal force - time O(kn^2); space O(kn)
#         dp = [[float('inf')] * (N+1) for _ in range(K+1)]
#         for egg_num in range(1, K+1):
#             dp[egg_num][0] = 0
#             dp[egg_num][1] = 1
#         for floor_num in range(1, N+1):
#             dp[1][floor_num] = floor_num
        
#         for egg_num in range(2, K+1):
#             for floor_num in range(2, N+1):
#                 for start_floor in range(1, floor_num+1):
#                     dp[egg_num][floor_num] = min(dp[egg_num][floor_num], 1+max(dp[egg_num-1][start_floor-1], dp[egg_num][floor_num-start_floor]))
#         print(dp)
#         return dp[K][N]
    
        # time - O(nk) for declare and O(klogn) for running; space O(nk)
        dp = [[0] * (K+1) for _ in range(N+1)]
        for m in range(1, N+1):
            for k in range(1, K+1):
                dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1
            if dp[m][K] >= N:
                return m

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp_dict = dict()
        
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in dp_dict:
                return dp_dict[(K, N)]
            ans = inf
            
            # # normal
            # for i in range(1, N+1):
            #     ans = min(ans, max(dp(K-1, i-1), dp(K,N-i))+1)
            # dp_dict[(K, N)] = ans
            # return ans
            
            # binary
            low, high = 1, N
            while low <= high:
                mid = (high + low) // 2
                broken = dp(K-1, mid-1)
                good = dp(K, N-mid)
                if broken > good:
                    high = mid - 1
                    ans = min(broken+1, ans)
                else:
                    low = mid + 1
                    ans = min(good+1, ans)
            dp_dict[(K, N)] = ans
            return ans
            
        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # https://leetcode.com/problems/super-egg-drop/discuss/443089/Simplest-Python-DP-Solution-with-Detailed-Explanation-99Time-100Mem
        # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
        # M = 300 # big enough number
        # dp = [[0 for j in range(K+1)] for i in range(M+1)]
        # # Initialization 1 --> no move no floor --> dp[0][*] = 0
        # # Initialization 2 --> no egg no floor --> dp[*][0] = 0
        # # General case --> we want to find dp[m][k] --> we pick one egg and drop (1 move)
        # #              --> now we have k or k-1 eggs, depending on whether the previous egg is broken
        # #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
        # for i in range(1, M+1):
        #     for j in range(1, K+1):
        #         dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
        #         if dp[i][j] >= N:
        #             return i
        memo = dict()    
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in memo:
                return memo[(K, N)]
            res = float('inf')
            low, high = 1, N+1
            while low < high:
                mid = (low + high)//2
                broken = dp(K-1, mid -1)
                notBroken = dp(K, N-mid)
                if broken > notBroken:
                    high = mid
                    res = min(broken + 1, res)
                else:
                    low = mid + 1
                    res = min(notBroken + 1, res)    
            # for i in range(1, N+1):
            #     res = min(res, \\
            #               max(dp(K-1, i-1), dp(K, N-i))+ 1)
            memo[(K,N)] = res
            return res
        return dp(K, N)
            
                
            


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        DP = range(N + 1)
        for k in range(2, K + 1):
            DP2 = [0]
            x = 1
            for n in range(1, N+1):
                while x < n and max(DP[x-1], DP2[n - x]) > max(DP[x], DP2[n - x - 1]):
                    x += 1
                    
                DP2.append(1 + max(DP[x-1], DP2[n - x]))
            
            DP = DP2
            
        return DP[-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo={}
        def dp(K,N):
            if K==1:
                return N
            if N==0:
                return 0
            if (K,N) in memo:
                return memo[(K,N)]
            res=float('inf')
            l,h=1,N
            while l<=h:
                mid=(l+h)//2
                broken=dp(K-1,mid-1)
                not_broken=dp(K,N-mid)
                if broken>not_broken:
                    h=mid-1
                    res=min(res,1+broken)
                else:
                    l=mid+1
                    res=min(res,1+not_broken)
            memo[(K,N)]=res        
            return res
        return dp(K,N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            
            if (K, N) in memo:
                return memo[(K, N)]
            
            res = float('inf')
            
            lo, hi = 1, N
            
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                broken = dp(K-1, mid - 1)
                not_broken = dp(K, N - mid)
                
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            
            # for i in range(1, N+1):
            #     res = min(res,
            #              max(
            #                  dp(K, N-i), 
            #                  dp(K-1, i-1)
            #                 ) + 1
            #              )
            
            memo[(K, N)] = res
            
            return res
        
        return dp(K, N)

# K and N is suitation
# choice: need to choose drop egg on which floor
# use binary search to optimize complexity
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(K: int, N: int):
            # base case
            if N == 0:
                return 0
            if K == 1:
                return N
            if (K, N) in memo:
                return memo[(K, N)]
            res = float('inf')
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res
        return dp(K, N)




class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo={}
    
        def dp(k, n):
            if n==0:
                return 0
            if k==1:
                return n
            if (k,n) in memo:
                return memo[(k,n)]
            res=float('inf')
            lo=1
            hi=n
            while lo<=hi:
                mid=(lo+hi)//2
                broken=dp(k-1,mid-1)
                not_broken=dp(k,n-mid)
                if broken>not_broken:
                    hi=mid-1
                    res=min(res,broken+1)
                else:
                    lo=mid+1
                    res=min(res,not_broken+1)
            # for i in range(1,n+1):
            #     res=min(res,max(dp(k-1,i-1), dp(k,n-i))+1)
            memo[(k,n)]=res
            return res
        return dp(K,N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        memo = dict()
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            if (K, N) in memo:
                return memo[(K, N)]

            # for 1 <= i <= N:
            #     res = min(res, 
            #             max( 
            #                 dp(K - 1, i - 1), 
            #                 dp(K, N - i)      
            #                 ) + 1 
            #             )

            res = float('INF')
            # 用二分搜索代替线性搜索
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1) # 碎
                not_broken = dp(K, N - mid) # 没碎
                # res = min(max(碎，没碎) + 1)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        t = [[0]*(K+1) for _ in range(N+1)]
        for i in range(1,N+1):
            for j in range(1,K+1):
                t[i][j] = t[i-1][j] + t[i-1][j-1] + 1
                
            if t[i][j] >= N:
                return i

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo={}
        
        def dp(k,n):
            if k==1:
                return n
            if n==0:
                return 0
            if (k,n) in memo:
                return memo[(k,n)]
            
            res=float('INF')
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(k - 1, mid - 1) # 碎
                not_broken = dp(k, n - mid) # 没碎
                # res = min(max(碎， 没碎) + 1)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            
            memo[(k,n)]=res
            return res
        
        return dp(K,N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # https://leetcode.com/problems/super-egg-drop/discuss/443089/Simplest-Python-DP-Solution-with-Detailed-Explanation-99Time-100Mem
        # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
        # M = 300 # big enough number
        # dp = [[0 for j in range(K+1)] for i in range(M+1)]
        # # Initialization 1 --> no move no floor --> dp[0][*] = 0
        # # Initialization 2 --> no egg no floor --> dp[*][0] = 0
        # # General case --> we want to find dp[m][k] --> we pick one egg and drop (1 move)
        # #              --> now we have k or k-1 eggs, depending on whether the previous egg is broken
        # #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
        # for i in range(1, M+1):
        #     for j in range(1, K+1):
        #         dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
        #         if dp[i][j] >= N:
        #             return i
        memo = dict()    
        def dp(K, N):
            if K == 1:
                return N
            if N == 0:
                return 0
            if (K, N) in memo:
                return memo[(K, N)]
            res = float('inf')
            low, high = 1, N
            while low <= high:
                mid = (low + high)//2
                broken = dp(K-1, mid -1)
                notBroken = dp(K, N-mid)
                if broken > notBroken:
                    high = mid -1
                    res = min(broken + 1, res)
                else:
                    low = mid + 1
                    res = min(notBroken + 1, res)
            # res = float('inf')
            # low, high = 1, N+1
            # while low < high:
            #     mid = (low + high)//2
            #     broken = dp(K-1, mid -1)
            #     notBroken = dp(K, N-mid)
            #     if broken > notBroken:
            #         high = mid
            #         res = min(broken + 1, res)
            #     else:
            #         low = mid + 1
            #         res = min(notBroken + 1, res)    
            # for i in range(1, N+1):
            #     res = min(res, \\
            #               max(dp(K-1, i-1), dp(K, N-i))+ 1)
            memo[(K,N)] = res
            return res
        return dp(K, N)
            
                
            


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            if (K, N) in memo:
                return memo[(K, N)]
            
            res = float('INF')

            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1)
                not_broken = dp(K, N - mid) 
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        memo = dict()
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            if (K, N) in memo:
                return memo[(K, N)]

            res = float('INF')
            # 用二分搜索代替线性搜索
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1) # 碎
                not_broken = dp(K, N - mid) # 没碎
                # res = min(max(碎，没碎) + 1)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:

        memo = dict()
        def dp(K, N):
            if K == 1: return N
            if N == 0: return 0
            if (K, N) in memo:
                return memo[(K, N)]

            # for 1 <= i <= N:
            #     res = min(res, 
            #             max( 
            #                 dp(K - 1, i - 1), 
            #                 dp(K, N - i)      
            #                 ) + 1 
            #             )

            res = float('INF')
            # 用二分搜索代替线性搜索
            lo, hi = 1, N
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(K - 1, mid - 1) # 碎
                not_broken = dp(K, N - mid) # 没碎
                # res = min(max(碎，没碎) + 1)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)

            memo[(K, N)] = res
            return res

        return dp(K, N)


# K and N is suitation
# choice: need to choose drop egg on which floor
# use binary search to optimize complexity
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k: int, n: int):
            # base case
            if n == 0:
                return 0
            if k == 1:
                return n
            if (k, n) in memo:
                return memo[(k, n)]
            lo = 1
            hi = n
            res = float('inf')
            # we use binary search to speedup the process
            while lo <= hi:
                mid = (lo + hi) // 2
                broken = dp(k - 1, mid - 1)
                not_broken = dp(k, n - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                else:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
            # write into memo
            memo[(k, n)] = res
            return res
        return dp(K, N)





class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(K, N):
            if N == 0:
                return 0
            if K == 1:
                return N
            
            if (K, N) in memo:
                return memo[(K, N)]
            
            res = float('INF')
            
            # for i in range(1, N+1):
            #     res = min(res, max(dp(K-1, i-1),  dp(K, N-i))+1)
            
            lo, hi = 1, N
            
            while(lo <= hi):
                mid = lo + (hi - lo)//2
                broken = dp(K-1, mid-1)
                unbroken = dp(K, N - mid)
                if broken > unbroken:
                    hi = mid - 1
                    res = min(res, broken+1)
                else:
                    lo = mid + 1
                    res = min(res, unbroken+1)
            
            memo[(K, N)] = res
            return res
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # memo = {(1, n) : n for n in range(1, N + 1)}
        dp = [[0]*(K + 1) for _ in range(N + 1)]
        
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = max(dp[m][k], dp[m - 1][k] + 1 + dp[m - 1][k - 1])
            if dp[m][k] >= N:
                return m

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[None] * K for _ in range(N+1)]
        for j in range(K):
            dp[0][j] = 0
        for i in range(1, N+1):
            dp[i][0] = i
        for j in range(1, K):
            dp[1][j] = 1
            m = 1
            for i in range(2, N+1):
                while m < i and dp[i-m][j] >= dp[m-1][j-1] and dp[i-m-1][j] >= dp[m][j-1]:
                    m += 1
                dp[i][j] = max(dp[i-m][j], dp[m-1][j-1]) + 1
                # for m in range(1, i+1):
                #     dp[i][j] = min(dp[i][j], max(dp[m-1][j-1], dp[i-m][j]) + 1)
        return dp[N][K-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        
        return self.dp(K, N, memo)
    
    def dp(self, k, n, memo):
        if k == 1: return n 
        if n == 0: return 0
        if (k, n) in memo:
            return memo[(k, n)]
        res = float('inf')
        '''
        for i in range(1, n+1):
            res = min(res,  max(self.dp(k-1, i-1, memo), self.dp(k, n-i, memo)) + 1 )
        '''
        lo, hi = 1, n
        while lo <= hi:
            mid = lo + (hi - lo)//2
            broken = self.dp(k-1, mid-1, memo)
            not_broken = self.dp(k, n-mid, memo)
            
            if broken > not_broken:
                hi = mid - 1
                res = min(res, broken + 1)
            else:
                lo = mid + 1
                res = min(res, not_broken + 1)
        memo[(k, n)] = res
        
        return res


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # base case for only 1 egg
        dp=list(range(N+1))
        for k in range(1,K):
            newdp=[0]
            opt=1
            for n in range(1,N+1):
                # the optimum choice (intersection of two values) increases with n
                tmp=max(dp[opt-1],newdp[n-opt])
                while opt<n and tmp>max(dp[opt],newdp[n-opt-1]):
                    tmp=max(dp[opt],newdp[n-opt-1])
                    opt+=1                    
                newdp.append(1+tmp)
            dp=newdp
        return dp[-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        cache = {}
        return self.drop_iter(K, N, cache)

    def drop_iter(self, K, N, cache):
        if K == 1:
            return N
        if N == 0:
            return 0
        if (K, N) in cache:
            return cache[(K, N)]
        res = float('inf')
        # for i in range(1, N+1):
        #     temp = max(self.drop_iter(K, N-i, cache), self.drop_iter(K-1, i-1, cache)) + 1
        #     res = min(res, temp)
        left = 1
        right = N
        # self.drop_iter(K, N-i, cache) 单调减
        # self.drop_iter(K-1, i-1, cache) 单调增
        while left <= right:
            mid = (left + right) // 2
            borke = self.drop_iter(K - 1, mid - 1, cache)
            not_broke = self.drop_iter(K, N - mid, cache)
            if borke > not_broke:
                right = mid - 1
                res = min(borke + 1, res)
            else:
                left = mid + 1
                res = min(not_broke + 1, res)

        cache[(K, N)] = res
        return res

        



class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = range(N + 1)
        for k in range(2, K+1):
            dp2 = [0]
            x = 1
            for n in range(1, N+1):
                while x < n and max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1]):
                    x += 1
                dp2.append(1+max(dp[x-1], dp2[n-x]))
            dp = dp2
        
        return dp[-1]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp = [[0] * (K+1) for n in range(N+1)]
        for m in range(1,N+1):
            for k in range(1,K+1):
                dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1
            if dp[m][k] >= N: return m


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        m = [[0 for i in range(N + 1)] for j in range(K + 1)]
        
        def find(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if m[k][n] > 0:
                return m[k][n]
            
            def bsearch():
                st, end = 1, n
                while st <= end:
                    m = (st + end) // 2
                    if predicate(m):
                        end = m - 1
                    else:
                        st = m + 1
                return st, end
             
            def predicate(x):
                return True if find(k-1, x - 1) >= find(k, n - x) else False

            st, end = bsearch()
            v_st = max(find(k - 1,st - 1), find(k, n - st)) if st <= N else math.inf
            v_end = max(find(k - 1, end - 1), find(k, n - end)) if end >= 1 else math.inf
            
            m[k][n] = min(v_st, v_end) + 1
            return m[k][n]
        
        return find(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        cachedSolutions = [[-1 for i in range(N+1)] for j in range(K+1)]
        return self.getMinDrops(K, N, cachedSolutions)

    def getMinDrops(self, eggs, floors, cachedSolutions):
        if cachedSolutions[eggs][floors] > 0:
            return cachedSolutions[eggs][floors]
        elif eggs == 0:
            cachedSolutions[eggs][floors] = 0
            return 0
        elif eggs == 1 or floors <= 2:
            cachedSolutions[eggs][floors] = floors
            return floors
        else:
            ## Arbitrarily large number to initialize the minimum number of drops.
            smallestIndex = 1
            largestIndex = floors
            minDrops = 100000000
            while(smallestIndex<=largestIndex):
                ## We want to find the minimum of the maximums of all possible subproblems and do it through binary search.
                middleIndex = round(smallestIndex+(largestIndex-smallestIndex)/2)
                ## Solve the subproblems.
                minDropsA = self.getMinDrops(eggs-1, middleIndex-1, cachedSolutions)
                minDropsB = self.getMinDrops(eggs, floors-middleIndex, cachedSolutions)
                ## Find a new minimum number of drops for validating that all floors are a solution or not.
                tempMinDrops = max(minDropsA, minDropsB) + 1
                minDrops = min(minDrops, tempMinDrops)
                ## Check which half will contain the valid solution.
                if (minDropsA > minDropsB):
                    largestIndex = middleIndex - 1
                else:
                    smallestIndex = middleIndex + 1
            cachedSolutions[eggs][floors] = minDrops
        return cachedSolutions[eggs][floors]



class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        m = [[0 for i in range(N + 1)] for j in range(K + 1)]
        
        def find(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if m[k][n] > 0:
                return m[k][n]
            
            def bsearch():
                st, end = 1, n
                while st <= end:
                    m = (st + end) // 2
                    if predicate(m):
                        end = m - 1
                    else:
                        st = m + 1
                return st, end
             
            def predicate(x):
                return True if find(k-1, x - 1) >= find(k, n - x) else False

            st, end = bsearch()
            if st > N:
                v_st = math.inf
                v_end = 1 + max(find(k - 1, end - 1), find(k, n - end))
            elif end < 1:
                v_end = math.inf
                v_st = 1 + max(find(k - 1,st - 1), find(k, n - st))
            else:
                v_st = 1 + max(find(k - 1,st - 1), find(k, n - st))
                v_end = 1 + max(find(k - 1, end - 1), find(k, n - end))
            
            m[k][n] = min(v_st, v_end)
            return m[k][n]
        
        return find(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (K + 1) for i in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: return m

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (K+1) for _ in range(N+1)]
        
        for move in range(1, N+1):
            for egg in range(1, K+1):
                dp[move][egg] = dp[move - 1][egg - 1] + dp[move - 1][egg] + 1
                
            if dp[move][K] >= N:
                return move

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (K + 1) for i in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: return m


# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,l):
    s = 0
    c = 1
    for i in range(1,k+1):
        c *= (l-i+1)/(i)
        s += c
    return s

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

def f(K, x):
    ans = 0
    r = 1
    for i in range(1, K+1):
        r *= x-i+1
        r //= i
        ans += r
    return ans

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        a, b = 1, n
        while a < b:
            c = (a+b)//2
            if fast_sum(k,c) < n:
                a = c + 1
            else:
                b = c
        return a

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,l):
    s = 0
    c = 1
    for i in range(1,k+1):
        c *= (l-i+1)/(i)
        s += c
    return s

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

def f(K, x):
    ans = 0
    r = 1
    for i in range(1, K+1):
        r *= x-i+1
        r //= i
        ans += r
    return ans

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        l = 0
        while fast_sum(k, l) < n:
            l+=1
        return l

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
#         results = [[None for _ in range(N+1)] for _ in range(K+1)]
#         def dp(K, N):
#             if K == 1:
#                 return N
#             if N == 0:
#                 return 0
            
#             if results[K][N]:
#                 return results[K][N]
            
            
#             res = N
            
#             left = 1
#             right = N
            
#             while left <= right:
#                 mid = int((right+left)/2)
                
#                 broken_num = dp(K-1, mid-1)
#                 notbroken_num = dp(K, N-mid)
#                 if broken_num > notbroken_num:
#                     right = mid - 1
#                     res = min(res, broken_num + 1)
#                 else:
#                     left = mid + 1
#                     res = min(res, notbroken_num + 1)
            
#             results[K][N] = res
#             # for i in range(1, N+1):
#             #     results[K][N] = min(results[K][N], max(dp(K-1, i-1), dp(K, N-i)) + 1)
            
#             # return results[K][N]
#             return res
#         # dp(K, N)
#         # print(results)
#         return dp(K, N)

        dp = [[0 for _ in range(N+1)] for _ in range(K+1)]
    
        m = 0
        while dp[K][m] < N:
            m += 1
            for k in range(1, K+1):
                dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1
                
        return m

class Solution:
    def superEggDrop(self, K, N):
        dp = [0, 0]
        m = 0
        while dp[-1] < N:
            for i in range(len(dp) - 1, 0, - 1):
                dp[i] += dp[i - 1] + 1
            if len(dp) < K + 1:
                dp.append(dp[-1])
            m += 1
        return m

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,n):
    s = 0
    c = 1
    for i in range(1,k+1):
        c *= (n-i+1)/(i)
        s += c
    return s

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

def f(K, x):
    ans = 0
    r = 1
    for i in range(1, K+1):
        r *= x-i+1
        r //= i
        ans += r
    return ans

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        l = 0
        while fast_sum(k, l) < n:
            l+=1
        return l

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,l,n):
    s = 0
    c = 1
    for i in range(1,k+1):
        c *= (l-i+1)/(i)
        s += c
        if s >= n:
            return s
    return s

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

def f(K, x):
    ans = 0
    r = 1
    for i in range(1, K+1):
        r *= x-i+1
        r //= i
        ans += r
    return ans

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        l = 0
        while fast_sum(k, l, n) < n:
            l+=1
        return l

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # dp[k][m]: given k eggs, max move m, the highest floor can find F
        # dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
        # max m will be N, linear scan
        
        dp = [[0 for i in range(N + 1)] for j in range(K + 1)]
        m = 0
        while dp[K][m] < N:
            m += 1
            for k in range(1, K + 1):
                dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
        return m
        


# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,l):
    s = 0
    c = 1
    for i in range(1,k+1):
        c *= (l-i+1)/(i)
        s += c
    return s

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

def f(K, x):
    ans = 0
    r = 1
    for i in range(1, K+1):
        r *= x-i+1
        r //= i
        ans += r
    return ans

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        a, b = 1, n
        while a < b:
            c = (a+b)//2
            if h2(k,c) < n:
                a = c + 1
            else:
                b = c
        return a

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # dp[k][m] means the number floors can be identify when using k egges with maximum try m times 
        dp = [[0 for col in range(N + 2)] for row in range(K + 2)]
        m = 0
        while dp[K][m] < N:
            m += 1
            for k in range(1, K + 1):
                dp[k][m] = dp[k - 1][m - 1] + dp[k][m - 1] + 1
                
        return m
        
        
#         def dp(k, n):
#             if k == 1:
#                 return n
#             if n == 0:
#                 return 0
#             if (k, n) in memo:
#                 return memo[(k, n)]
            
#             res = sys.maxsize
#             lo, hi = 1, n
#             while lo <= hi:
#                 mid = (lo + hi) // 2
#                 broken = dp(k - 1, mid - 1) 
#                 safe = dp(k, n - mid) 
#                 if broken > safe:
#                     hi = mid - 1
#                     res = min(res, broken + 1)
#                 else:
#                     lo = mid + 1
#                     res = min(res, safe + 1)
                    
#             memo[(k, n)] = res
#             return res
        
#         memo = {}
#         return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
#         dpDict = {}
        
#         def dp(K,N):
#             if K == 1: return N
#             if N == 0: return 0
#             if (K, N) in dpDict: return dpDict[K,N] 
#             res = float('inf')
#             for i in range(1, N + 1):
#                 res = min(res, 
#                           1 + max(dp(K-1, i-1), dp(K,N-i))
#                          )
                
#             dpDict[K,N] = res
#             return res
        
#         return dp(K,N)
                
        dp = [[0 for _ in range(N+1)] for _ in range(K+1)]
        m = 0
        while dp[K][m] < N:
            m += 1
            for i in range(1,K+1):
                dp[i][m] = dp[i][m-1] + dp[i-1][m-1] + 1
        return m

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        l = 0
        while h2(k, l) < n:
            l+=1
        return l

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        best_case = floor(log2(n)+1)
        if k >= best_case:
            return best_case
        l = 0
        while h2(k, l) < n:
            l+=1
        return l

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # dp[M][K]means that, given K eggs and M moves, what is the maximum number of floor that we can check.
        dp = [[0] * (K + 1) for i in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: 
                return m

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        '''
        # Top down: Time O(KN log(N)) Space O(KN)
        import functools
        @functools.lru_cache(None)
        def dp(k, m):
            if k == 1: return m
            if m == 1: return 1
            return dp(k-1, m-1) + dp(k, m-1) + 1
        l, r = 1, N
        while l < r:
            mid = (l+r) // 2
            if dp(K, mid) >= N:
                r = mid
            else:
                l = mid + 1
        return l
        '''
        # Bottom up: Time O(Klog(N)) Space O(K)
        dp, ndp = {}, {}
        for m in range(1, N+1):
            for k in range(1, K+1):
                if m == 1: ndp[k] = 1
                elif k == 1: ndp[k] = m
                else:
                    ndp[k] = dp[k-1] + dp[k] + 1
                if ndp[k] >= N:
                    return m
            dp, ndp = ndp, {}


# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def h2(k,n):
    return sum(comb(n,j) for j in range(1,k+1))

def fast_sum(k,n):
    c = n
    for i in range(k):
        c *= (n-k)/(k+1)
    return c

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        # best_case = floor(log2(n)+1)
        # if k >= best_case:
        #     return best_case
        if k == 0:
            return n
        l = 0
        while h2(k, l) < n:
            l+=1
        return l

class Solution:
    def superEggDrop(self, eggs: int, floors: int) -> int:
        dp = [[0] * (eggs+1) for _ in range(floors+1)]
        currFloor = 0
        
        while dp[currFloor][eggs] < floors:
            currFloor += 1
            for i in range(1 , eggs+1):
                dp[currFloor][i] = dp[currFloor - 1][i-1] + dp[currFloor - 1][i] + 1
                
        return currFloor

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp = [[0 for _ in range(N +1)] for _ in range(K + 1)]
        
        m = 0
        while dp[K][m] < N:
            m += 1
            
            for k in range(1, K + 1):
                dp[k][m] = 1 + dp[k-1][m-1] + dp[k][m-1]
        
        return m


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp=[[0]*(K+1) for i in range(N+1)]
        for m in range(1,N+1):
            for k in range(1,K+1):
                
                dp[m][k]=dp[m-1][k-1]+dp[m-1][k]+1
        
            if dp[m][K]>=N:
                return m


from math import comb


class Solution:
    def ncr(self,n, r):
        sum=0
        r=min(n,r)
        for l in range(1,r+1):
            sum+=comb(n,l)
        return sum
   
   
    def superEggDrop(self, K, N):
    
        matrix=[[0 for j in range(K)]for i in range(N)]
        for i in range(N):
            for j in range(K):
                matrix[i][j]=self.ncr(i+1,j+1)
                if matrix[i][K-1]>=N:
                    return i+1
        print(matrix)

           


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
        
        attempt = 0 
        while dp[attempt][K] < N:
            attempt += 1 
            for i in range(1, K+1):
                dp[attempt][i] = 1 + dp[attempt-1][i-1] + dp[attempt-1][i]
                if dp[attempt][i] >= N :
                    return attempt
        
        return attempt

from math import comb


class Solution:
    def ncr(self,n, r):
        sum=0
        r=min(n,r)
        for l in range(1,r+1):
            sum+=comb(n,l)
        return sum
   
   
    def superEggDrop(self, K, N):
    
        matrix=[[0 for j in range(K)]for i in range(N)]
        for i in range(N):
            for j in range(K):
                matrix[i][j]=self.ncr(i+1,j+1)
                if matrix[i][K-1]>=N:
                    return i+1
        print(matrix)
       
#         for m in range(N):
#             if matrix[m][K-1]>=N:
#                 return m+1

           


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                memo[m][k] = memo[m - 1][k - 1] + 1 + memo[m - 1][k]
                if memo[m][k] >= N: return m 

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
#         dp=[[0 for _ in range(K+1)] for _ in range(N+1)];
        
#         for n in range(N+1):
#             dp[n][0]=float('inf');
            
#         for k in range(K+1):
#             dp[0][k]=0;
            
        
#         for k in range(1,K+1):
#             for n in range(1,N+1):
#                 # res= float('inf');
#                 # for i in range(1,n+1):
#                 #     res= min(res, max(dp[i-1][k-1],dp[n-i][k]));
#                 # dp[n][k]=1+res;
                
#                 l=1;
#                 r=n;
                
#                 while(r-l>=2):
#                     mid=int((l+r)/2);
                    
#                     a= dp[mid-1][k-1];
#                     b= dp[n-mid][k];
                    
#                     if a>b:
#                         r=mid-1;
#                     elif a<b:
#                         l=mid+1;
#                     else:
#                         l,r=mid,mid;
                        
#                 dp[n][k]= 1 + min( max(dp[l-1][k-1],dp[n-l][k]) , max(dp[r-1][k-1],dp[n-r][k]));
                
#         return dp[N][K];



        # O(k*N) time
        
        dp= [[0 for _ in range(K+1)] for _ in range(N+1)];
        
        for n in range(1,N+1):
            for k in range(1,K+1):
                dp[n][k]=1 + dp[n-1][k] + dp[n-1][k-1];
            if dp[n][K]>=N:
                return n;

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dp(m, k):
            if m<=1 or k==1: return m
            if (m, k) in memo: return memo[(m, k)]
            
            memo[(m, k)] = dp(m-1, k-1)+1+dp(m-1, k)
            return memo[(m, k)]
        
        memo = {}
        for i in range(N+1):
            if dp(i, K)>=N:
                return i

class Solution:
    # def superEggDrop(self, K: int, N: int) -> int:
    #     drops = 0
    #     floors = [0] * (K + 1)
    #     while floors[K] < N:
    #         for eggs in range(K, 0, -1):
    #             floors[eggs] += 1 + floors[eggs - 1]
    #         drops += 1
    #     return drops

    def superEggDrop(self, K: int, N: int) -> int:
            # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
            M = N # big enough number
            dp = [[0 for j in range(K+1)] for i in range(M+1)]
            # Initialization 1 --> no move no floor --> dp[0][*] = 0
            # Initialization 2 --> no egg no floor --> dp[*][0] = 0
            # General case --> we want to find dp[m][k] --> we pick one egg and drop (1 move)
            #              --> now we have k or k-1 eggs, depending on whether the previous egg is broken
            #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
            for i in range(1, M+1):
                for j in range(1, K+1):
                    dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
                    if dp[i][j] >= N:
                        return i

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        dp = [ [0 for j in range(K+1)] for i in range(N+1)]
        
        attempt = 0
        while(dp[attempt][K]<N):
            attempt+=1
            for j in range(1,len(dp[0])):
                dp[attempt][j]= 1 + dp[attempt-1][j-1]+ dp[attempt-1][j]
                if dp[attempt][j]>=N:
                    return attempt
        
                


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        drops = 0
        floors = [0] * (K + 1)
        while floors[K] < N:
            for eggs in range(K, 0, -1):
                floors[eggs] += 1 + floors[eggs - 1]
            drops += 1
        return drops

    def superEggDrop(self, K: int, N: int) -> int:
            # M x K --> Given M moves and K eggs, what is the maximum floor we can check ?
            M = N # big enough number
            dp = [[0 for j in range(K+1)] for i in range(M+1)]
            #              --> so in either case, we can at least sum up 1 (first move) + dp[m-1][k] + dp[m-1][k-1] 
            for i in range(1, M+1):
                for j in range(1, K+1):
                    dp[i][j] = 1 + dp[i-1][j] + dp[i-1][j-1]
                    if dp[i][j] >= N:
                        return i


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp=[[0 for i in range(K+1)]for i in range(N+1)]
        for m in range(1,N+1):
            for k in range(1,K+1):
                dp[m][k]=1+dp[m-1][k-1]+dp[m-1][k]
            if dp[m][k]>=N: 
                return m
        #return dp[-1][-1]


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0 for i in range(K + 1)] for j in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k]
            if dp[m][K] >= N:
                return m 
        
                
                


import numpy as np
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # given K eggs and M moves, what is the maximum number of floor that we can check.
        dp = [[0 for i in range(K+1)] for j in range(N+1)]
        for i in range(1, N+1):
            for j in range(1, K+1):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1
            if dp[i][j] >= N:
                return i
                
                
                
#         #Dec1, 2019
#         self.grid = np.zeros((K+1, N+1), dtype=np.int32)
#         return self.drop(K, N)
        
#     def drop(self, K, N):
#         for j in range(1, N+1):
#             for i in range(1, K+1):
#                 self.grid[i][j] = self.grid[i-1][j-1] + self.grid[i][j-1] + 1
#             if self.grid[K][j] >= N: #if we could already check all stairs with K eggs, then return the number of stairs j
#                 return j
#         return self.grid[K][N]
        

#         #Dec1, 2019
#         self.grid = np.zeros((K+1, N+1), dtype=np.int32)
#         return self.test(K, N)
        
        
#     def test(self, K, N):
#         if N == 1 or N == 0:
#             return N
#         elif K == 1 or K == 0:
#             return N
#         else:
#             if self.grid[K][N]:
#                 return self.grid[K][N]
#             else:
#                 self.grid[K][N] = min(max(self.test(K-1, i-1), self.test(K, N-i)) for i in range(1, N+1))+1
#                 return self.grid[K][N]


#O(N*K)
#O(1)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        #find max no of floor you can reach with given eggs and no of attempts
        
        dp = [ [0 for j in range(K+1)] for i in range(N+1)]
        
        attempt = 0
        while(dp[attempt][K]<N):
            attempt+=1
            for j in range(1,len(dp[0])):
                # 1 + Break case + No Break case
                dp[attempt][j]= 1 + dp[attempt-1][j-1]+ dp[attempt-1][j]
                if dp[attempt][j]>=N:
                    return attempt
        
                


from functools import lru_cache
from typing import Tuple

class Solution:
    # floor: 0 <= F <= N
    # Ans f where eggs break if it's higher than f
    # N floors from 1 to N.
    # K eggs
    # Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N). 
    def superEggDrop(self, K: int, N: int) -> int:
        return superEggHelper(K, N)
        
            
        
        
        
@lru_cache(maxsize=None)
def superEggHelper(K: int, N: int) -> int:
    # base case
    if N == 0:
        return 0
    
    if K == 1:
        return N

    # ans = N;
    # dropping from floor i
    # for i in range(1, N + 1):
    #     ans = min(max(superEggHelper(K, N - i), superEggHelper(K - 1, i - 1)) + 1, ans)

    # bin search
    ans = bisectEggHelper(K, 1, N, N)

    # print(K, N, ans)
    return ans

# 2 0 1 1
# S: start, E: end, N: number of floors, K: number of eggs
def bisectEggHelper(K: int, S: int, E: int, N: int) -> int:
    # print(K, S, E, N)
    # base case, only one element left
    if S == E:
        left, right = superEggCalc(K, S, N)
        return max(left, right) + 1
    
    # base case, only two elements left
    if S + 1 == E:
        # K = 2
        # i = 0
        # S = 0
        # N = 1
        left1, right1 = superEggCalc(K, S, N)
        left2, right2 = superEggCalc(K, E, N)
        return min(max(left1, right1), max(left2, right2)) + 1

    # choose i = (S + E) // 2
    i = (S + E) // 2
    left, right = superEggCalc(K, i, N)
    if left > right:
        return bisectEggHelper(K, S, i, N)
    else:
        return bisectEggHelper(K, i, E, N)
   
def superEggCalc(K: int, i: int, N: int) -> Tuple:
    return (superEggHelper(K - 1, i - 1), superEggHelper(K, N - i))


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(1, N+1))
        for _ in range(K-1):
            temp = [1]
            for j in range(1, N):
                if temp[-1] >= N:
                    break
                temp.append(temp[-1]+dp[j-1]+1)
            dp = temp
        return len(dp)

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

from scipy.special import comb, factorial, hyp2f1
from math import log2, floor

def h(k,n):
    return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

def e(k, n):
    if k == 1:
        return n
    return sum(e(k-1, j)+1 for j in range(n))

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        best_case = floor(log2(n)+1)
        if k >= best_case:
            return best_case
        l = 0
        while e(k, l) < n:
            l+=1
        return l

class Solution:
    @lru_cache(None)
    def superEggDrop(self, k: int, n: int) -> int:
        if n == 0:
            return 0
        elif k == 1:
            return n
        
        lo, hi = 1, n
        while lo < hi:
            mid = (lo + hi) // 2
            r1, r2 = self.superEggDrop(k-1, mid-1), self.superEggDrop(k, n - mid)
            if r1 > r2:
                hi = mid
            elif r1 < r2:
                lo = mid + 1
            else:
                lo = hi = mid
        return 1 + max(self.superEggDrop(k-1, lo-1), self.superEggDrop(k, n-lo))
        



class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        #6:00
        # if we have 1 one egg
        # we will need N attempts
        
        # if we have 2 egg
        # pick start postion as any k
        # if it breaks
        # then we will need f(k-1,1)
        # if it doesn't break f(n-k+1,2)
        @lru_cache(None)
        def helper(floors,eggs):
            if floors<=0:return 0
            if eggs==1:return floors
            # pick k
            ans=floors
            low,high=1,floors
            while low+1<high:
                # we dont low, high to be together
                mid=low+(high-low)//2
                t1=helper(mid-1,eggs-1)
                t2=helper(floors-mid,eggs)
                if t1<t2:
                    low=mid
                elif t1>t2:
                    high=mid
                else:
                    low=high=mid
            ans=floors
            for k in (low,high):
                ans=min(ans,1+max(helper(k-1,eggs-1),helper(floors-k,eggs)))
                
                
            
#             for k in range(1,floors+1):
#                 # can it be binary search? i think graph has to be symmetric
                
#                 ans=min(ans,1+max(helper(k-1,eggs-1),helper(floors-k,eggs)))
            return ans
        return helper(N,K)
        
        
        
        
        
        
        


from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(maxsize=None)
        def dp(K: int, N: int) -> int:
            if N==0:
                return 0
            elif K==1:
                return N
            else:
                l,r=1,N
                res=N
                while l+1<r:
                    X=(l+r)//2
                    f1=dp(K,N-X)
                    f2=dp(K-1,X-1)
                    if f1<f2:
                        r=X
                    elif f1==f2:
                        l=r=X
                    else:
                        l=X
                return 1+min(max(dp(K-1,X-1),dp(K,N-X)) for X in (l,r))  
        return dp(K,N)


import sys
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        val = Solution.dp(K,N)
        return val
    __memo = dict()
    def dp(K,N):
        if K == 1:
            return N
        if N == 0:
            return 0
        if (K,N) in Solution.__memo:
            return Solution.__memo[(K,N)]
        res = sys.maxsize
        lo, hi = 1, N
        while lo <= hi:
            mid = (lo + hi) // 2
            broken = Solution.dp(K - 1, mid - 1) # 碎
            not_broken = Solution.dp(K, N - mid) # 没碎
            # res = min(max(碎，没碎) + 1)
            if broken > not_broken:
                hi = mid - 1
                res = min(res, broken + 1)
            else:
                lo = mid + 1
                res = min(res, not_broken + 1)

        Solution.__memo[(K,N)] = res
        return res
        


t = [[-1 for i in range(10001)] for j in range(101)]

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        if N == 0 or N == 1:
            return N

        if K == 1:
            return N

        if t[K][N] != -1:
            return t[K][N]

        mn, l, h = sys.maxsize, 1, N
        while l <= h:
            mid = (l + h) // 2

            down_temp = self.superEggDrop(K - 1, mid - 1)
            up_temp = self.superEggDrop(K, N - mid)

            res = 1 + max(down_temp, up_temp)

            if down_temp < up_temp:
                l = mid + 1
            else:
                h = mid - 1

            mn = min(mn, res)

        t[K][N] = mn

        return mn

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dict_soln = {}
        return self.dp(K, N, dict_soln)
    def dp(self, k, n, dict_soln):
        if n == 0:
            return 0
        if k == 0:
            return -1
        if k == 1:
            return n
        if (k, n) in dict_soln:
            return dict_soln[(k, n)]
        # test at x (x = 1, ..., n)
        # dp(k, n) = min_{x = 1, ..., n} max(dp(k, n - x), dp(k - 1, x - 1)) + 1
        left = 1
        right = n
        while True:
            if left - right == -1:
                tmp1 = self.dp(k - 1, left - 1, dict_soln)
                tmp2 = self.dp(k, n - left, dict_soln)
                tmp3 = self.dp(k - 1, right - 1, dict_soln)
                tmp4 = self.dp(k, n - right, dict_soln)
                tmpl = max(tmp1, tmp2)
                tmpr = max(tmp3, tmp4)
                if tmpl < tmpr:
                    dict_soln[(k, n)] = tmpl + 1
                    return dict_soln[(k, n)]
                else:
                    dict_soln[(k, n)] = tmpr + 1
                    return dict_soln[(k, n)]
            xmid = (left + right) // 2
            tmp1 = self.dp(k - 1, xmid - 1, dict_soln)
            tmp2 = self.dp(k, n - xmid, dict_soln)
            if tmp1 > tmp2:
                right = xmid
            elif tmp1 < tmp2:
                left = xmid
            else:
                dict_soln[(k, n)] = tmp1 + 1
                return dict_soln[(k, n)]
            
    
        
        


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = dict()
        def dp(k, n):
            # base case
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in memo:
                return memo[(k, n)]
            res = float('inf')
            # for i in range(1, n + 1):
            #     res = min(res, max(dp(k, n - i), dp(k - 1, i - 1)) + 1)
            lo, hi = 1, n
            while lo <= hi:
                mid = lo + (hi - lo) // 2
                broken = dp(k - 1, mid - 1)
                not_broken = dp(k, n - mid)
                if broken > not_broken:
                    hi = mid - 1
                    res = min(res, broken + 1)
                elif not_broken > broken:
                    lo = mid + 1
                    res = min(res, not_broken + 1)
                elif not_broken == broken:
                    res = min(res, broken + 1)
                    break
            memo[(k, n)] = res
            return res
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        
        ### state: dp[k][m]. 如果有K个鸡蛋，最多能抛m次，那么最多可以确定的F最高为几层楼
        ### transfer: 如果在某一层楼丢鸡蛋，要不就是碎了，要不就是没碎。 
        #### 碎了：说明得测楼下： dp[k-1][m-1]为最多能测落下的层数
        #### 没碎：说明得测楼上： dp[k][m-1]为最多能测楼上的层数
        ####不管碎还是没碎，总共能测的层数= 楼下 + 楼上 + 1（现在那一层）
        #### dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1
        #### 每当有一个m值的时候，我们也要从k=1 到k=K去simulate，去填充dp里面的值（dp来自上面和左上角）
        
        ### init: base case是什么呢？比如K=0的时候，肯定测0层。 m=0的时候，也测0层
        #### dp[0][...] = 0; dp[...][0] = 0
        
        ### result: 当dp[K][m] == N 的时候，m就是我们想要的答案. K是大写K，因为我们一开始就有K个鸡蛋
        
        dp = [[0]*(N+1) for i in range(K+1)]

        m = 0
        while dp[K][m] < N:
            m += 1
            
            for i in range(1, K+1):
                dp[i][m] = dp[i][m-1] + dp[i-1][m-1] + 1
                
        
        return m

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k, n):
            if (k, n) in memo: return memo[(k, n)]
            if k == 1:
                return n
            if n == 0:
                return 0
            start = 1
            end = n
            res = float('inf')
            while start <= end:
                mid = (start+end)//2
                pre = dp(k-1, mid-1)+1
                cur = dp(k, n-mid)+1
                if pre < cur:
                    res = min(res, cur)
                    start = mid+1
                elif pre > cur:
                    res = min(res, pre)
                    end = mid-1
                else:
                    res = pre
                    break
            memo[(k, n)] = res
            return res
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(1, N+1))
        for _ in range(K-1):
            temp = [1]
            for j in range(1, N):
                temp.append(temp[-1]+dp[j-1]+1)
            dp = temp
        for i in range(N):
            if dp[i] >= N:
                return i+1

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(1, N+1))
        for _ in range(K-1):
            temp = [1]
            for j in range(1, N):
                temp.append(temp[-1]+dp[j-1]+1)
            dp = temp
        return [i+1 for i, x in enumerate(dp) if x >= N][0]

from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        # return self.bottomUp(K, N)
        # return self.findMoves(K, N)
        return self.bottomUp2(K, N)
    
    @lru_cache(maxsize = None)
    def findMoves(self, K, N):
        if K == 1 or N<=1:
            return N
        
        left, right = 1, N
        while left < right:
            mid = (left + right) // 2
            
            broken = self.findMoves(K-1, mid-1)
            intact = self.findMoves(K, N-mid)
            if broken > intact:
                right = mid
            else:
                left = mid+1
        
        mid = left -1
        return 1 + max(self.findMoves(K-1, mid-1), self.findMoves(K, N-mid))

        # f = N            
        # for x in range (1, N+1):
        #     f = min(1 + max(self.findMoves(K-1, x-1), self.findMoves(K, N-x)), f)
        # return f
    
    def bottomUp(self, K, N):
        # compress to 1d array
        dp = [i for i in range(N+1)]
        for i in range(2, K+1):
            prev = dp[:]
            for j in range(1, N+1):
                min_drops = N
                for x in range(1, j+1):
                    min_drops = min(min_drops, 1 + max(prev[x-1], dp[j-x]))
                dp[j] = min_drops
        print(dp)
        return dp[N]
    
    def bottomUp2(self, K, N):
        dp = [i for i in range(N+1)]
        
        for i in range(2, K+1):
            broken = dp[1]
            for i in range(2, N+1):
                prev = dp[i]
                dp[i] = 1+dp[i-1]+broken
                broken = prev
        
        left, right = 1, N
        while left < right:
            mid = (left + right) // 2
            if dp[mid] >= N:
                right = mid
            left = left + 1
        
        return left

class Solution:
    def binary_search(self,A,k,n):
        lo = 0
        hi = n
        mid = (lo+hi)//2
        while lo<hi:
            if A[k-1][mid-1]==A[k][n-mid]:
                return mid
            if A[k-1][mid-1]>A[k][n-mid]:
                hi = mid
            else:
                lo = mid+1
            mid = (lo+hi)//2
            
        return lo
    def superEggDrop(self, K: int, N: int) -> int:
        if N==1:
            return 1
        k=0
        n=N
        while n>0:
            k+=1
            n//=2
        if K>k:
            return k
        A = [[0 for n in range(N+1)] for k in range(K+1)]
        
        for n in range(N+1):
            A[1][n] = n
        for k in range(K+1):
            A[k][1] = 1
            A[k][2] = 2
        
        for k in range(2,K+1):
            low=1
            for n in range(3,N+1):
                # linear search
                # m=1
                # while A[k-1][m-1]<A[k][n-m]:
                #     m+=1
                
                #binary search
                # m = self.binary_search(A,k,n)
                # A[k][n] = 1+max(A[k-1][m-1],A[k][n-m])
                
                # tip-toe
                # print('k =',k,' n = ',n,low,'    ', A[k-1][low],'   ',A[k][n-low-1],'   ',A[k][n])
                if A[k-1][low]<A[k][n-low-1]:
                    low+=1
                  
                A[k][n] = 1+A[k-1][low]
                # print('k =',k,' n = ',n,low,'    ', A[k-1][low],'   ',A[k][n-low-1],'   ',A[k][n])
                # print('')
        return A[-1][-1]

class Solution:
    def binary_search(self,A,k,n):
        lo = 0
        hi = n
        mid = (lo+hi)//2
        while lo<hi:
            if A[k-1][mid-1]==A[k][n-mid]:
                return mid
            if A[k-1][mid-1]>A[k][n-mid]:
                hi = mid
            else:
                lo = mid+1
            mid = (lo+hi)//2
            
        return lo
    def superEggDrop(self, K: int, N: int) -> int:
        if N==1:
            return 1
        k=0
        n=N
        while n>0:
            k+=1
            n//=2
        if K>k:
            return k
        A = [[0 for n in range(N+1)] for k in range(K+1)]
        
        for n in range(N+1):
            A[1][n] = n
        for k in range(K+1):
            A[k][1] = 1
            A[k][2] = 2
        
        for k in range(2,K+1):
            low=1
            for n in range(3,N+1):
                # linear search
                # m=1
                # while A[k-1][m-1]<A[k][n-m]:
                #     m+=1
                
                #binary search
                # m = self.binary_search(A,k,n)
                # A[k][n] = 1+max(A[k-1][m-1],A[k][n-m])
                
                # tip-toe
                if A[k-1][low]<A[k][n-low-1]:
                    low+=1
                  
                A[k][n] = 1+A[k-1][low]
        return A[-1][-1]

#class Solution:
#    def superEggDrop(self, K: int, N: int) -> int:
#        def solve(e,f,dp):
#            if f==0:
#                return f
#            elif e==1:
#                return f
#         
#            if dp[e][f]!=-1:
#                return dp[e][f]
#            l,h=1,f
#            while l+1<h:
#                x=(l+h)//2
#                if dp[e][f-x]!=-1:
#                    f1=dp[e][f-x]
#                else:
#                    f1=solve(e,f-x,dp)
#                if dp[e-1][x-1]!=-1:
#                    f2=dp[e-1][x-1]
#                else:
#                    f2=solve(e-1,x-1,dp)
#                if f1<f2:
#                    l=x
#                elif f2>f1:
#                    h=x
#                else:
#                    l=h=x
#            
#            ans=1+min(max(solve(e,f-x,dp),solve(e,x-1,dp)) for x in range(l,h+1))
#            dp[e][f]=ans    
#            return dp[e][f]
#        dp=[[-1]*(N+1) for i in range(K+1)]
#        return solve(K,N,dp)
class Solution(object):
    def superEggDrop(self, K, N):
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0 or n==1:
                    ans = n
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x
                    ans=1000000
                    for x in range(lo, hi+1):
                            temp=1+max(dp(k-1, x-1), dp(k, n-x))
                            if ans>temp:
                                ans=temp
                    
                    

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

#class Solution:
#    def superEggDrop(self, K: int, N: int) -> int:
#        def solve(e,f,dp):
#            if f==0:
#                return f
#            elif e==1:
#                return f
#         
#            if dp[e][f]!=-1:
#                return dp[e][f]
#            l,h=1,f
#            while l+1<h:
#                x=(l+h)//2
#                if dp[e][f-x]!=-1:
#                    f1=dp[e][f-x]
#                else:
#                    f1=solve(e,f-x,dp)
#                if dp[e-1][x-1]!=-1:
#                    f2=dp[e-1][x-1]
#                else:
#                    f2=solve(e-1,x-1,dp)
#                if f1<f2:
#                    l=x
#                elif f2>f1:
#                    h=x
#                else:
#                    l=h=x
#            
#            ans=1+min(max(solve(e,f-x,dp),solve(e,x-1,dp)) for x in range(l,h+1))
#            dp[e][f]=ans    
#            return dp[e][f]
#        dp=[[-1]*(N+1) for i in range(K+1)]
#        return solve(K,N,dp)
class Solution(object):
    def superEggDrop(self, K, N):
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x
                    ans=1000000
                    for x in range(lo, hi+1):
                            temp=1+max(dp(k-1, x-1), dp(k, n-x))
                            if ans>temp:
                                ans=temp
                    
                    

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

class Solution:
    def superEggDrop(self, K, N):
        dp = dict()
        def recursive(k, n):
            if k == 1:
                return n
            if n == 0:
                return 0
            if (k, n) in dp:
                return dp[(k, n)]

            res = float('INF')
            l = 1
            r = n + 1
            while l <= r:
                m = int((l + r) / 2)
                v1 = recursive(k, n - m)
                v2 = recursive(k - 1, m - 1)
                res = min(res, max(v1, v2) + 1)
                if v1 < v2:
                    r = m - 1
                elif v1 > v2:
                    l = m + 1
                else:
                    break

            dp[(k, n)] = res
            return res

        import sys
        sys.setrecursionlimit(3000)
        res = recursive(K, N)
        return res

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = {}
        def helper(K, N):
            if N <= 2:
                return N
            if K == 1:
                return N

            if (K, N) not in dp:
                l = 1
                r = N
                while l + 1 < r:
                    mid = (l + r) // 2
                    # if egg breaks at midpoint, try egg drop for lower floors
                    die = helper(K - 1, mid - 1)
                    # if egg survives, try egg drop for higher floors
                    live = helper(K, N - mid)
                    
                    if die < live:
                        l = mid
                    elif die > live:
                        r = mid
                    else:
                        l = r = mid
                dp[(K, N)] = 1 + min([max(helper(K - 1, l - 1), helper(K, N - l)), max(helper(K - 1, r - 1), helper(K, N - r))])
            return dp[(K, N)]
        
        return helper(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        max_floors = [0 for _ in range(N + 1)]

        for k in range(1, K + 1):
            next_max_floors = [0 for _ in range(N + 1)]
            for t in range(1, N + 1):
                next_max_floors[t] = 1 + max_floors[t - 1] + next_max_floors[t - 1]
            max_floors = next_max_floors
        for t in range(N):
            if max_floors[t] >= N:
                return t
        return N


class Solution:
    def __init__(self):
        self.memo = {}

    def superEggDrop(self, K: int, N: int) -> int:

        def solve(K, N):
            d = self.memo.get((K, N))

            if d is None:
                if K == 1 or N <= 2:
                    # 1) K == 1: Only one egg is left.
                    # Drop egg from bottom floor up until it breaks.
                    # Maximum N drops.
                    # 2) N <= 2: Simple cases that don't need binary search.
                    # Same strategy as above.
                    d = N

                else:
                    A_min = 1
                    A_max = N

                    while A_max - A_min > 1:
                        A = (A_min + A_max) // 2
                        t1 = solve(K - 1, A - 1)
                        t2 = solve(K, N - A)

                        if t1 > t2:
                            A_max = A
                        elif t2 > t1:
                            A_min = A
                        else:
                            A_min = A_max = A

                    d = 1 + min(
                        max(
                            self.memo[K - 1, A - 1],
                            self.memo[K, N - A]
                        )
                        for A in [A_min, A_max]
                    )

                self.memo[K, N] = d

            return d

        return solve(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = {}
        def helper(K, N):
            if N <= 1:
                dp[(K, N)] = N
            if K == 1:
                dp[(K, N)] = N

            if (K, N) not in dp:
                l = 1
                r = N
                while l + 1 < r:
                    mid = (l + r) // 2
                    # if egg breaks at midpoint, try egg drop for lower floors
                    die = helper(K - 1, mid - 1)
                    # if egg survives, try egg drop for higher floors
                    live = helper(K, N - mid)
                    
                    if die < live:
                        l = mid
                    elif die > live:
                        r = mid
                    else:
                        l = r = mid
                dp[(K, N)] = 1 + min([max(helper(K - 1, l - 1), helper(K, N - l)), max(helper(K - 1, r - 1), helper(K, N - r))])
            return dp[(K, N)]
        
        return helper(K, N)

# class Solution:
#     def superEggDrop(self, K: int, N: int) -> int:    
#         def segment_sum(x,k):
#             # x is worst case, k is number of eggs available
#             # returns max N for worst case x, eggs k
#             if k==1:
#                 return x
#             return sum(segment_sum(j, k-1)+1 for j in range(x))

#         worst_case=0
#         while segment_sum(worst_case, K) < N:
#             worst_case+=1
#         return worst_case

# class Solution(object):
#     def superEggDrop(self, K, N):
#         drops = 0                           # the number of eggs dropped
#         floors = [0 for _ in range(K + 1)]  # floors[i] is the number of floors that can be checked with i eggs

#         while floors[K] < N:                # until we can reach N floors with K eggs 

#             for eggs in range(K, 0, -1):
#                 floors[eggs] += 1 + floors[eggs - 1]
#             drops += 1

#         return drops

# class Solution(object):
#     def superEggDrop(self, K, N):
#         def f(x):
#             ans = 0
#             r = 1
#             for i in range(1, K+1):
#                 r *= x-i+1
#                 r //= i
#                 ans += r
#                 if ans >= N: break
#             return ans

#         lo, hi = 1, N
#         while lo < hi:
#             mi = (lo + hi) // 2
#             if f(mi) < N:
#                 lo = mi + 1
#             else:
#                 hi = mi
#         return lo

# from scipy.special import comb, factorial, hyp2f1
# from math import log2, floor

# def h(k,n):
#     return round(2**n-1-comb(n,k+1)*hyp2f1(1,k-n+1,k+2,-1))

# def h2(k,n):
#     return sum(comb(n,j) for j in range(1,k+1))

# def fast_sum(k,l):
#     s = 0
#     c = 1
#     for i in range(1,k+1):
#         c *= (l-i+1)/(i)
#         s += c
#     return s

# def e(k, n):
#     if k == 1:
#         return n
#     return sum(e(k-1, j)+1 for j in range(n))
from math import floor, log2
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        best_case = floor(log2(n)+1)
        if k >= best_case:
            return best_case
        def fast_sum(k,l):
            s = 0
            c = 1
            for i in range(k):
                c *= (l-i)/(i+1)
                s += c
            return s
        if k == 0:
            return n
        a, b = 1, n
        while a < b:
            c = (a+b)//2
            if fast_sum(k,c) < n:
                a = c + 1
            else:
                b = c
        return a

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(n, k):
            if (n, k) not in memo:
                if n == 0:
                    ret = 0
                elif k == 1:
                    ret = n
                else:
                    lo, hi = 1, n
                    while lo+1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(n-x, k)
                        t2 = dp(x-1, k-1)
                        if t1 < t2:
                            hi = x
                        elif t1 > t2:
                            lo = x
                        else:
                            lo = hi = x
                    ret = 1 + min(max(dp(n-x, k), dp(x-1, k-1)) for x in (lo, hi))
                
                memo[n, k] = ret
            return memo[n, k]
        
        return dp(N, K)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    while lo + 1 < hi:
                        x = lo + (hi - lo) // 2
                        t1 = dp(k - 1, x - 1)
                        t2 = dp(k, n - x)
                        
                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x
                    ans = 1 + min(max(dp(k - 1, x - 1), dp(k, n - x)) for x in (lo, hi))
                memo[(k, n)] = ans
            return memo[(k, n)]
        return dp(K, N)


class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        INF = N + 1
        cache = {}
        
        def eggDropHelper(k, n):
            if (k, n) in cache:
                return cache[(k, n)]
            if (k < 0):
                return INF
            if (n == 0):
                return 0
            if (k == 0):
                return INF
            optAns = INF
            l, r = 1, n
            while ((l + 1) < r):
                m = (l + r) // 2
                left, right = eggDropHelper(k - 1, m - 1), eggDropHelper(k, n - m)
                if (left < right):
                    l = m
                elif (left > right):
                    r = m
                else:
                    l = r = m
                    break
            optAns = max(eggDropHelper(k - 1, l - 1), eggDropHelper(k, n - l)) + 1
            currAns = max(eggDropHelper(k - 1, r - 1), eggDropHelper(k, n - r)) + 1
            optAns = min(currAns, optAns)
            cache[(k, n)] = optAns
            return cache[(k, n)]
            
        return eggDropHelper(K, N)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        memo = {}
        def dp(k, n):
            ans = 0
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    l, r = 1, n
                    while l + 1 < r:
                        x = (l + r)//2
                        t1 = dp(k - 1, x - 1)
                        t2 = dp(k, n - x)
                        if t1 > t2:
                            r = x
                        elif t1 < t2:
                            l = x
                        else:
                            l = r = x
                    ans = 1 + min(max(dp(k - 1, x - 1), dp(k, n - x)) for x in (l, r))
                memo[(k, n)] = ans
            return memo[(k, n)]
        return dp(K, N)


class Solution:
    def superEggDrop(self, K, N):
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x

                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x)) for x in (lo, hi))

                memo[k, n] = ans
            return memo[k, n]

        return dp(K, N)

class Solution(object):
    def superEggDrop(self, K, N):
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n <= 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) >> 1
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x
                            # ans = t1
                    # if lo == hi:
                    #     ans = t1
                    # else:
                    #     ans = min(t1,t2)
                    # print(lo,hi)
                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x)) for x in (lo, hi))

                memo[k, n] = ans
                return memo[k, n]
            else:
                return memo[k, n]

        return dp(K, N)

class Solution:
    def superEggDrop(self, K, N):
        memo = {}
        def dp(k, n):
            if (k, n) not in memo:
                if n == 0:
                    ans = 0
                elif k == 1:
                    ans = n
                else:
                    lo, hi = 1, n
                    # keep a gap of 2 X values to manually check later
                    while lo + 1 < hi:
                        x = (lo + hi) // 2
                        t1 = dp(k-1, x-1)
                        t2 = dp(k, n-x)

                        if t1 < t2:
                            lo = x
                        elif t1 > t2:
                            hi = x
                        else:
                            lo = hi = x

                    ans = 1 + min(max(dp(k-1, x-1), dp(k, n-x))
                                  for x in (lo, hi))

                memo[k, n] = ans
            return memo[k, n]
        return dp(K, N)