You are given N identical eggs and you have access to a K-floored building from 1 to K.
There exists a floor f where 0 <= f <= K 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. There are few rules given below. 
	An egg that survives a fall can be used again.
	A broken egg must be discarded.
	The effect of a fall is the same for all eggs.
	If the egg doesn't break at a certain floor, it will not break at any floor below.
	If the eggs breaks at a certain floor, it will break at any floor above.
Return the minimum number of moves that you need to determine with certainty what the value of f is.
For more description on this problem see wiki page
Example 1:
Input:
N = 1, K = 2
Output: 2
Explanation: 
1. Drop the egg from floor 1. If it 
   breaks, we know that f = 0.
2. Otherwise, drop the egg from floor 2.
   If it breaks, we know that f = 1.
3. If it does not break, then we know f = 2.
4. Hence, we need at minimum 2 moves to
   determine with certainty what the value of f is.
Example 2:
Input:
N = 2, K = 10
Output: 4
Your Task:
Complete the function eggDrop() which takes two positive integer N and K as input parameters and returns the minimum number of attempts you need in order to find the critical floor.
Expected Time Complexity : O(N*(K^2))
Expected Auxiliary Space: O(N*K)
Constraints:
1<=N<=200
1<=K<=200

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    
    #Function to find minimum number of attempts needed in 
    #order to find the critical floor.
    def eggDrop(self,n, k):
        # code here

Solutions:
class Solution:

	def eggDrop(self, e, f):
		dp = [0 for i in range(e + 1)]
		m = 0
		while dp[e] < f:
			m += 1
			for x in range(e, 0, -1):
				dp[x] += 1 + dp[x - 1]
		return m


class Solution:

	def eggDrop(self, e, f):
		dp = [[0] * (f + 1) for _ in range(e + 1)]
		for i in range(1, e + 1):
			dp[i][1] = 1
			dp[i][0] = 0
		for i in range(1, f + 1):
			dp[1][i] = i
		for i in range(2, e + 1):
			for j in range(2, f + 1):
				dp[i][j] = float('inf')
				lo = 1
				hi = j
				while lo <= hi:
					mid = lo + (hi - lo) // 2
					egg_broken = dp[i - 1][mid - 1]
					egg_not_broken = dp[i][j - mid]
					dp[i][j] = min(dp[i][j], 1 + max(egg_broken, egg_not_broken))
					if egg_broken < egg_not_broken:
						lo = mid + 1
					else:
						hi = mid - 1
		return dp[e][f]


class Solution:

	def fn(self, e, f, memo):
		if f == 0 or f == 1:
			return f
		if e == 1:
			return f
		if memo[e][f] != -1:
			return memo[e][f]
		mn = float('inf')
		for k in range(1, f + 1):
			broken = self.fn(e - 1, k - 1, memo)
			not_broken = self.fn(e, f - k, memo)
			tmp = 1 + max(broken, not_broken)
			mn = min(mn, tmp)
		memo[e][f] = mn
		return memo[e][f]

	def eggDrop(self, e, f):
		memo = [[-1 for i in range(f + 1)] for j in range(e + 1)]
		return self.fn(e, f, memo)


class Solution:

	def eggDrop(self, n, k):
		dp = [[1 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if i == 1:
					dp[i][j] = j
				elif i > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = 1000000
					for e in range(1, j):
						res = 1 + max(dp[i - 1][e - 1], dp[i][j - e])
						if res < dp[i][j]:
							dp[i][j] = res
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):

		def solve(i, k, dp):
			if i == 1:
				return k
			if k == 0 or k == 1:
				return k
			if dp[i][k] != -1:
				return dp[i][k]
			mini = 9999
			b_nb = 0
			for ki in range(1, k + 1):
				option1 = solve(i - 1, ki - 1, dp)
				option2 = solve(i, k - ki, dp)
				b_nb = 1 + max(option1, option2)
				mini = min(b_nb, mini)
			dp[i][k] = mini
			return dp[i][k]
		dp = [[-1] * (k + 1) for _ in range(n + 1)]
		return solve(n, k, dp)


class Solution:

	def eggDrop(self, n, k):
		cache = [[-1 for _ in range(n + 1)] for i in range(k + 1)]

		def dfs(eggs, floor):
			if eggs == 1:
				return floor
			elif floor == 0 or floor == 1:
				return floor
			elif cache[floor][eggs] == -1:
				currVal = float('inf')
				for i in range(1, floor + 1):
					val = 1 + max(dfs(eggs - 1, i - 1), dfs(eggs, floor - i))
					currVal = min(currVal, val)
				cache[floor][eggs] = currVal
			return cache[floor][eggs]
		return dfs(n, k)


class Solution:

	def eggDrop(self, n, k):
		dp = []
		for i in range(n + 1):
			temp = [-1] * (k + 1)
			dp.append(temp)

		def solve(n, k):
			if n == 0 or k == 0:
				return 0
			if n == 1:
				return k
			if k == 1:
				return 1
			if dp[n][k] != -1:
				return dp[n][k]
			mn = float('inf')
			for i in range(1, k + 1):
				tmp = max(solve(n - 1, i - 1), solve(n, k - i))
				if tmp < mn:
					mn = tmp
			dp[n][k] = mn + 1
			return dp[n][k]
		return solve(n, k)


class Solution:

	def eggDrop(self, n, k):
		dp = [[0] * (k + 1) for _ in range(n + 1)]

		def solve(n, k):
			if n == 1 or k == 1 or k == 0:
				return k
			if dp[n][k] != 0:
				return dp[n][k]
			ans = float('inf')
			for i in range(1, k):
				c1 = solve(n - 1, i - 1)
				c2 = solve(n, k - i)
				worst = 1 + max(c1, c2)
				ans = min(ans, worst)
			dp[n][k] = ans
			return ans
		return solve(n, k)


INT_MAX = 32767

def eggDrop(n, k):
	eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
	for i in range(1, n + 1):
		eggFloor[i][1] = 1
		eggFloor[i][0] = 0
	for j in range(1, k + 1):
		eggFloor[1][j] = j
	for i in range(2, n + 1):
		for j in range(2, k + 1):
			eggFloor[i][j] = INT_MAX
			for x in range(1, j + 1):
				res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x])
				if res < eggFloor[i][j]:
					eggFloor[i][j] = res
	return eggFloor[n][k]

class Solution:

	def eggDrop(self, n, k):
		return eggDrop(n, k)


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
		for i in range(1, k + 1):
			dp[1][i] = i
		for i in range(1, n + 1):
			dp[i][1] = 1
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				mini = float('inf')
				if i > j:
					dp[i][j] = dp[i - 1][j]
				else:
					for p in range(1, j + 1):
						mini = min(mini, 1 + max(dp[i - 1][p - 1], dp[i][j - p]))
					dp[i][j] = mini
		return dp[n][k]


class Solution:

	def eggDrop(self, e, f):
		dp = []
		for i in range(e + 1):
			p = []
			for j in range(f + 1):
				p.append(1)
			dp.append(p)
		for i in range(1, e + 1):
			for j in range(1, f + 1):
				if i == 1:
					dp[i][j] = j
				elif i > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = 100000.0
					for k in range(1, j):
						res = 1 + max(dp[i - 1][k - 1], dp[i][j - k])
						if res < dp[i][j]:
							dp[i][j] = res
		return dp[e][f]


class Solution:

	def solve(self, n, k, dp):
		if dp[k][n] != -1:
			return dp[k][n]
		min = float('inf')
		if k == 1 or k == 0:
			return k
		if n == 1:
			return k
		for x in range(1, k + 1):
			res = max(self.solve(n - 1, x - 1, dp), self.solve(n, k - x, dp))
			if res < min:
				min = res
		dp[k][n] = min + 1
		return min + 1

	def eggDrop(self, n, k):
		dp = [[-1 for i in range(n + 1)] for j in range(k + 1)]
		a = self.solve(n, k, dp)
		return a


import math

class Solution:

	def eggDrop(self, n, k):
		dp = [[0] * (k + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(k + 1):
				if i == 1:
					dp[i][j] = j
				elif j == 0:
					dp[i][j] = 0
				else:
					min = math.inf
					counter = 0
					for x in range(j):
						curr = max(dp[i - 1][0 + x], dp[i][j - 1 - x])
						if curr < min:
							min = curr
					dp[i][j] = 1 + min
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for i in range(k + 1)] for i in range(n + 1)]

		def rec(n, k):
			if n == 1 or k == 1 or k == 0:
				return k
			if dp[n][k] != -1:
				return dp[n][k]
			mini = float('inf')
			for i in range(1, k + 1):
				egg_broken = rec(n - 1, i - 1)
				egg_survive = rec(n, k - i)
				maxi = max(egg_broken, egg_survive)
				mini = min(mini, 1 + maxi)
			dp[n][k] = mini
			return dp[n][k]
		for i in range(k + 1):
			dp[1][i] = i
		for i in range(2, n + 1):
			for j in range(1, k + 1):
				mini = float('inf')
				for f in range(1, j + 1):
					egg_broken = dp[i - 1][f - 1]
					egg_survive = dp[i][j - f]
					maxi = max(egg_broken, egg_survive)
					mini = min(mini, 1 + maxi)
				dp[i][j] = mini
		return dp[n][k]


import sys

class Solution:

	def eggDrop1(self, n, k):
		global dp
		if k == 0 or k == 1:
			return k
		if n == 1:
			return k
		if dp[n][k] != -1:
			return dp[n][k]
		maxans = sys.maxsize
		for i in range(1, k + 1):
			temp = 1 + max(self.eggDrop1(n, k - i), self.eggDrop1(n - 1, i - 1))
			maxans = min(temp, maxans)
		dp[n][k] = maxans
		return dp[n][k]

	def eggDrop(self, n, k):
		global dp
		dp = [[-1 for i in range(k + 1)] for j in range(n + 1)]
		return self.eggDrop1(n, k)


class Solution:

	def eggDrop(self, n, k):
		cover = [0] * (n + 1)
		moves = 0
		while cover[n] < k:
			moves += 1
			for eggs in range(n, 0, -1):
				cover[eggs] += 1 + cover[eggs - 1]
		return moves


class Solution:

	def eggDrop(self, n, k):
		cover = [[0] * (k + 1) for _ in range(n + 1)]
		for floor in range(k + 1):
			cover[1][floor] = floor
		for eggs in range(2, n + 1):
			for m in range(1, k + 1):
				cover[eggs][m] = 1 + cover[eggs - 1][m - 1] + cover[eggs][m - 1]
		for move in range(1, k + 1):
			if cover[n][move] >= k:
				return move
		cover = [0] * (n + 1)
		moves = 0
		while cover[n] < k:
			moves += 1
			for eggs in range(1, n + 1):
				cover[eggs] += 1 + cover[eggs - 1]
		return moves


class Solution:

	def eggDrop(self, n, k):
		maxi = 10 ** 9
		dp = [[-1] * (k + 1) for _ in range(n + 1)]

		def find(n, k):
			if n == 0:
				return 0 if k == 0 else maxi
			if n == 1 or k < 2:
				return k
			if dp[n][k] != -1:
				return dp[n][k]
			ans = maxi
			for i in range(1, k + 1):
				e_break = 1 + find(n - 1, i - 1)
				not_break = 1 + find(n, k - i)
				ans = min(ans, max(e_break, not_break))
			dp[n][k] = ans
			return dp[n][k]
		return find(n, k)


import sys

class Solution:

	def helper(self, eg, fl, dp):
		if fl == 1 or fl == 0:
			return fl
		if eg == 1:
			return fl
		if dp[eg][fl] != -1:
			return dp[eg][fl]
		ans = sys.maxsize
		for i in range(1, fl + 1):
			res = 1 + max(self.helper(eg - 1, i - 1, dp), self.helper(eg, fl - i, dp))
			ans = min(ans, res)
		dp[eg][fl] = ans
		return dp[eg][fl]

	def eggDrop(self, e, f):
		dp = [[-1] * (f + 1) for _ in range(e + 1)]
		return self.helper(e, f, dp)


import sys

class Solution:

	def eggDrop(self, e, f):
		dp = [[1] * (f + 1) for _ in range(e + 1)]
		for i in range(1, e + 1):
			dp[i][1] = 1
			dp[i][0] = 0
		for i in range(1, f + 1):
			dp[1][i] = i
		for i in range(2, e + 1):
			for j in range(2, f + 1):
				dp[i][j] = sys.maxsize
				for x in range(1, j + 1):
					res = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
					if res < dp[i][j]:
						dp[i][j] = res
		return dp[e][f]


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][1] = 1
		for i in range(1, k + 1):
			dp[1][i] = i
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				dp[i][j] = float('inf')
				for x in range(1, j + 1):
					res = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
					if res < dp[i][j]:
						dp[i][j] = res
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][1] = 1
		for i in range(1, k + 1):
			dp[1][i] = i
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				dp[i][j] = 25000
				for x in range(1, j + 1):
					res = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
					if res < dp[i][j]:
						dp[i][j] = res
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):

		def breakegg(n, k, dp):
			if k == 0 or k == 1:
				return k
			if n == 1:
				return k
			if dp[n][k] != -1:
				return dp[n][k]
			res = 1000000000.0
			for x in range(1, k + 1):
				b = max(1 + breakegg(n - 1, x - 1, dp), 1 + breakegg(n, k - x, dp))
				res = min(res, b)
			dp[n][k] = res
			return res
		dp = [[-1] * (k + 1) for _ in range(n + 1)]
		return breakegg(n, k, dp)


class Solution:

	def eggDrop(self, n, k):

		def egg_drop(n, k, dp):
			key = (n, k)
			if n == 1:
				return k
			if k <= 1:
				return k
			if key in dp:
				return dp[key]
			else:
				v = float('inf')
				for f in range(1, k + 1):
					temp1 = egg_drop(n - 1, f - 1, dp)
					temp2 = egg_drop(n, k - f, dp)
					temp = 1 + max(temp1, temp2)
					v = min(temp, v)
				dp[key] = v
				return dp[key]
		dp = dict()
		res = egg_drop(n, k, dp)
		return res


class Solution:

	def helper(self, eggs, floor, dp):
		if floor == 0 or floor == 1:
			return floor
		if eggs == 1:
			return floor
		if dp[eggs][floor] != -1:
			return dp[eggs][floor]
		ans = 10000000007
		for k in range(1, floor + 1):
			temp = 1 + max(self.helper(eggs - 1, k - 1, dp), self.helper(eggs, floor - k, dp))
			ans = min(ans, temp)
		dp[eggs][floor] = ans
		return ans

	def eggDrop(self, n, k):
		dp = [[-1] * 200] * 200
		return self.helper(n, k, dp)


class Solution:

	def eggDrop(self, n, k):
		dp = [[0] * (n + 1) for _ in range(k + 1)]
		m = 0
		while dp[m][n] < k:
			m += 1
			for e in range(1, n + 1):
				dp[m][e] = 1 + dp[m - 1][e] + dp[m - 1][e - 1]
		return m


class Solution:

	def eggDrop(self, e, f):
		t = [[-1 for i in range(f + 1)] for _ in range(e + 1)]

		def solve(e, f):
			if f == 0 or f == 1:
				return f
			if e == 1:
				return f
			if t[e][f] != -1:
				return t[e][f]
			mn = float('inf')
			for k in range(1, f + 1):
				if t[e - 1][k - 1] != -1:
					breaked = solve(e - 1, k - 1)
				else:
					breaked = solve(e - 1, k - 1)
					t[e - 1][k - 1] = breaked
				if t[e][f - k] != -1:
					notbreaked = t[e][f - k]
				else:
					notbreaked = solve(e, f - k)
					t[e][f - k] = notbreaked
				temp = 1 + max(breaked, notbreaked)
				mn = min(temp, mn)
			t[e][f] = mn
			return mn
		return solve(e, f)


class Solution:

	def eggDrop(self, n, k):
		dp = {}

		def solve(e, f):
			if (e, f) in dp:
				return dp[e, f]
			if f <= 1:
				return f
			if e == 1:
				return f
			mini = 99999999999
			for k in range(1, f + 1):
				temp = 1 + max(solve(e - 1, k - 1), solve(e, f - k))
				mini = min(temp, mini)
				dp[e, f] = mini
			return dp[e, f]
		return solve(n, k)


class Solution:

	def eggDrop(self, k, n):
		self.arr = [[None] * (n + 1) for i in range(k + 1)]
		return self.recur(k, n)

	def recur(self, k, n):
		x = 1000000000
		if self.arr[k][n]:
			return self.arr[k][n]
		if n == 0:
			return 0
		if k == 1 or n == 1:
			return n
		for i in range(1, n):
			p1 = self.recur(k, n - i)
			p2 = self.recur(k - 1, i - 1)
			p = 1 + max(p1, p2)
			x = min(x, p)
		self.arr[k][n] = x
		return x


class Solution:

	def eggDrop(self, n, k):
		dp = [[-1 for i in range(k + 1)] for j in range(n + 1)]

		def rec(n, k):
			if n == 1 or k == 0 or k == 1:
				return k
			if dp[n][k] != -1:
				return dp[n][k]
			mini = float('inf')
			for i in range(1, k + 1):
				egg_broken = rec(n - 1, i - 1)
				egg_survive = rec(n, k - i)
				maxi = max(egg_broken, egg_survive)
				mini = min(1 + maxi, mini)
			dp[n][k] = mini
			return dp[n][k]
		return rec(n, k)
		dp = [[0] * (k + 1) for _ in range(n + 1)]
		moves = 0
		while dp[n][moves] < k:
			moves += 1
			for i in range(1, n + 1):
				dp[i][moves] = 1 + dp[i - 1][moves - 1] + dp[i][moves - 1]
		return moves


class Solution:

	def eggDrop(self, n, k):
		dp = [[0] * (k + 1) for _ in range(n + 1)]
		moves = 0
		while dp[n][moves] < k:
			moves += 1
			for i in range(1, n + 1):
				dp[i][moves] = 1 + dp[i - 1][moves - 1] + dp[i][moves - 1]
		return moves


class Solution:

	def eggDrop(self, n, k):
		t = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]

		def solve(e, f):
			if f == 0 or f == 1:
				return f
			if e == 1:
				return f
			if t[e][f] != -1:
				return t[e][f]
			mn = float('inf')
			for i in range(1, f + 1):
				if t[e - 1][i - 1] != -1:
					low = t[e - 1][i - 1]
				else:
					low = solve(e - 1, i - 1)
					t[e - 1][i - 1] = low
				if t[e][f - i] != -1:
					high = t[e][f - i]
				else:
					high = solve(e, f - i)
					t[e][f - i] = high
				temp = 1 + max(low, high)
				mn = min(mn, temp)
			t[e][f] = mn
			return mn
		return solve(n, k)


class Solution:

	def solve(self, n, k, dp):
		if n == 1:
			return k
		if k == 0 or k == 1:
			return k
		if dp[n][k] != -1:
			return dp[n][k]
		res = 9999
		br_p = -9999
		for i in range(1, k):
			br_p = 1 + max(self.solve(n - 1, i - 1, dp), self.solve(n, k - i, dp))
			res = min(res, br_p)
		dp[n][k] = res
		return dp[n][k]

	def eggDrop(self, n, k):
		dp = [[-1 for i in range(k + 1)] for j in range(n + 1)]
		return self.solve(n, k, dp)


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for x in range(k + 1)] for y in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 0
			dp[i][1] = 1
		for j in range(1, k + 1):
			dp[1][j] = j
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				dp[i][j] = float('inf')
				(lo, hi) = (1, j)
				while lo <= hi:
					mid = (lo + hi) // 2
					if dp[i - 1][mid - 1] < dp[i][j - mid]:
						lo = mid + 1
					else:
						hi = mid - 1
				dp[i][j] = 1 + max(dp[i - 1][lo - 1], dp[i][j - lo])
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):
		dp = [[0] * (k + 1) for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(k + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif i == 1:
					dp[i][j] = j
				elif j == 1:
					dp[i][j] = 1
				else:
					ans = 100000000.0
					for l in range(1, j + 1):
						breaks = dp[i - 1][l - 1]
						nbreaks = dp[i][j - l]
						res = max(breaks, nbreaks)
						ans = min(ans, res)
					dp[i][j] = ans + 1
		return dp[-1][-1]


class Solution:

	def eggDrop(self, n, k):
		dp = [[None] * (n + 1) for i in range(k + 1)]
		for i in range(1, n + 1):
			dp[0][i] = 0
			dp[1][i] = 1
		for i in range(k + 1):
			dp[i][1] = i
		for i in range(2, k + 1):
			for j in range(2, n + 1):
				dp[i][j] = float('inf')
				for x in range(1, i + 1):
					temp = 1 + max(dp[x - 1][j - 1], dp[i - x][j])
					if temp < dp[i][j]:
						dp[i][j] = temp
		return dp[k][n]


import math

class Solution:

	def eggDrop(self, n, k):
		dp = {}

		def dfs(n, k):
			if k == 1 or k == 0:
				return k
			if n == 1:
				return k
			if (n, k) in dp:
				return dp[n, k]
			v = math.inf
			for x in range(1, k + 1):
				v = min(v, max(dfs(n - 1, x - 1), dfs(n, k - x)))
			dp[n, k] = v + 1
			return v + 1
		return dfs(n, k)


class Solution:

	def eggDrop(self, n, k):
		dp = [[-1 for j in range(k + 1)] for i in range(n + 1)]

		def solve(n, k):
			if dp[n][k] != -1:
				return dp[n][k]
			if k == 1 or k == 0:
				return k
			if n == 1:
				return k
			mn = int(1000000000.0)
			res = 0
			for x in range(1, k + 1):
				res = max(solve(n - 1, x - 1), solve(n, k - x))
				mn = min(mn, res)
			dp[n][k] = mn + 1
			return dp[n][k]
		return solve(n, k)


class Solution:

	def eggDrop(self, n, k):
		N = k
		K = n
		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 eggDrop(self, n, k):
		dp = [[0] * (k + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(k + 1):
				if i == 1 or j < 2:
					dp[i][j] = j
				else:
					z = float('inf')
					for l in range(1, j + 1):
						z = min(z, 1 + max(dp[i - 1][l - 1], dp[i][j - l]))
					dp[i][j] = z
		return dp[-1][-1]


class Solution:

	def eggDrop(self, n, k):
		dp = [[-1] * (k + 1) for _ in range(n + 1)]

		def solve(e, f):
			if e == 1 or f < 2:
				return f
			if dp[e][f] != -1:
				return dp[e][f]
			temp = float('inf')
			for k in range(1, f + 1):
				temp = min(temp, 1 + max(solve(e - 1, k - 1), solve(e, f - k)))
			dp[e][f] = temp
			return temp
		return solve(n, k)


from functools import lru_cache

class Solution:

	def eggDrop(self, eggs, floors):

		def f(e, floors):
			if e == 1:
				return floors
			if floors == 1 or floors == 0:
				return floors
			if dp[e][floors] != -1:
				return dp[e][floors]
			res = float('inf')
			for k in range(1, floors):
				res = min(res, max(f(e - 1, k - 1), f(e, floors - k)) + 1)
			dp[e][floors] = res
			return res
		dp = [[-1] * (floors + 1) for _ in range(eggs + 1)]
		return f(eggs, floors)


from functools import lru_cache

class Solution:

	def eggDrop(self, e, floors):

		@lru_cache(maxsize=1000000)
		def f(e, floors):
			if e == 1:
				return floors
			if floors == 1 or floors == 0:
				return floors
			res = float('inf')
			for k in range(1, floors):
				res = min(res, max(f(e - 1, k - 1), f(e, floors - k)) + 1)
			return res
		return f(e, floors)


class Solution:

	def eggDrop(self, n, k):

		def manu(n, k):
			if k == 0 or k == 1 or n == 1:
				return k
			if dp[n][k] != -1:
				return dp[n][k]
			mini = 10 ** 9
			for i in range(1, k):
				res = 1 + max(manu(n - 1, k - i), manu(n, i - 1))
				mini = min(mini, res)
			dp[n][k] = mini
			return mini
		dp = [[-1 for i in range(k + 1)] for i in range(n + 1)]
		return manu(n, k)


class Solution:

	def eggDrop(self, n, k):
		dp = [0] * (n + 1)
		m = 0
		while dp[n] < k:
			m += 1
			for x in range(n, 0, -1):
				dp[x] += 1 + dp[x - 1]
		return m


import math

class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for j in range(n + 1)] for i in range(k + 1)]
		for i in range(1, k + 1):
			dp[i][1] = i
		for j in range(1, n + 1):
			dp[1][j] = 1
		for i in range(2, k + 1):
			for j in range(2, n + 1):
				dp[i][j] = math.inf
				for x in range(1, i + 1):
					res = 1 + max(dp[x - 1][j - 1], dp[i - x][j])
					if res < dp[i][j]:
						dp[i][j] = res
		return dp[k][n]


import math

class Solution:

	def eggDrop(self, n, k):
		eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
		for i in range(1, n + 1):
			eggFloor[i][1] = 1
			eggFloor[i][0] = 0
		for j in range(1, k + 1):
			eggFloor[1][j] = j
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				eggFloor[i][j] = 1000000
				for x in range(1, j + 1):
					res = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x])
					if res < eggFloor[i][j]:
						eggFloor[i][j] = res
		return eggFloor[n][k]


class Solution:

	def util(self, egg, flr, dp):
		if dp[egg][flr] != -1:
			return dp[egg][flr]
		if egg == 1:
			return flr
		if flr == 0 or flr == 1:
			return flr
		ans = float('inf')
		for i in range(1, flr + 1):
			is_break = self.util(egg - 1, i - 1, dp)
			not_break = self.util(egg, flr - i, dp)
			worst_max = max(is_break, not_break)
			ans = min(worst_max, ans)
		dp[egg][flr] = ans + 1
		return dp[egg][flr]

	def eggDrop(self, n, k):
		dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]
		return self.util(n, k, dp)


def f(n, k, dp):
	if k == 1 or n == 0:
		return n
	if (n, k) in dp:
		return dp[n, k]
	ans = n + 1
	for l in range(1, n + 1):
		ans = min(ans, max(f(l - 1, k - 1, dp), f(n - l, k, dp)) + 1)
	dp[n, k] = ans
	return ans

class Solution:

	def eggDrop(self, n, k):
		dp = {}
		return f(k, n, dp)


class Solution:

	def eggDrop(self, n, k):
		dp = [[1 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if i == 1:
					dp[i][j] = j
				elif i > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = int(1000000000.0)
					for x in range(1, j):
						temp = 1 + max(dp[i - 1][x - 1], dp[i][j - x])
						if temp < dp[i][j]:
							dp[i][j] = temp
		return dp[n][k]


class Solution:

	def eggDrop(self, n, k):
		table = [[-1] * (k + 1) for i in range(n + 1)]

		def helper(n, k):
			if n == 1 or k == 0 or k == 1:
				return k
			if table[n][k] == -1:
				(mini, ans) = (201, -201)
				for i in range(1, k + 1):
					ans = 1 + max(helper(n - 1, i - 1), helper(n, k - i))
					mini = min(mini, ans)
				table[n][k] = mini
			return table[n][k]
		return helper(n, k)


class Solution:

	def eggDrop(self, e, f):
		dp = [[-1 for j in range(f + 1)] for i in range(e + 1)]
		return self.solve(e, f, dp)

	def solve(self, e, f, dp):
		if f == 1 or f == 0:
			return f
		if e == 1:
			return f
		if dp[e][f] != -1:
			return dp[e][f]
		mini = float('inf')
		for k in range(1, f + 1):
			temp_ans = 1 + max(self.solve(e - 1, k - 1, dp), self.solve(e, f - k, dp))
			mini = min(mini, temp_ans)
		dp[e][f] = mini
		return dp[e][f]


class Solution:

	def eggDrop(self, n, k):

		def solve(e, f):
			if f == 0 or f == 1:
				return f
			if e == 1:
				return f
			if tmp[e][f] != -1:
				return tmp[e][f]
			m = float('infinity')
			for k in range(1, f + 1):
				tmp1 = 1 + max(solve(e - 1, k - 1), solve(e, f - k))
				m = min(m, tmp1)
			tmp[e][f] = m
			return m
		tmp = [[-1] * 201 for i in range(201)]
		return solve(n, k)


class Solution:

	def eggDrop(self, n, k):
		eggFloor = [[0] * (k + 1) for i in range(n + 1)]
		for i in range(1, k + 1):
			eggFloor[1][i] = i
		for i in range(1, n + 1):
			eggFloor[i][0] = 0
			eggFloor[i][1] = 1
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				eggFloor[i][j] = float('inf')
				for x in range(1, j + 1):
					ans = 1 + max(eggFloor[i - 1][x - 1], eggFloor[i][j - x])
					if ans < eggFloor[i][j]:
						eggFloor[i][j] = ans
		return eggFloor[n][k]


class Solution:

	def eggDrop(self, n, k):
		dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][0] = 1
			dp[i][1] = 1
		for i in range(1, k + 1):
			dp[1][i] = i
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				dp[i][j] = float('inf')
				for k in range(1, j + 1):
					r = 1 + max(dp[i - 1][k - 1], dp[i][j - k])
					if r < dp[i][j]:
						dp[i][j] = r
		return dp[n][k]


class Solution:

	def eggDrop(self, n, floor):

		def helper(n, floor):
			if floor == 0 or floor == 1:
				return floor
			if n == 1:
				return floor
			if dp[n][floor] != -1:
				return dp[n][floor]
			min_mov = float('inf')
			for k in range(1, floor + 1):
				if dp[n - 1][k - 1] != -1:
					broken = dp[n - 1][k - 1]
				else:
					broken = helper(n - 1, k - 1)
					dp[n - 1][k - 1] = broken
				if dp[n][floor - k] != -1:
					not_broken = dp[n][floor - k]
				else:
					not_broken = helper(n, floor - k)
					dp[n][floor - k] = not_broken
				temp = 1 + max(broken, not_broken)
				min_mov = min(min_mov, temp)
			dp[n][floor] = min_mov
			return min_mov
		dp = [[-1 for j in range(floor + 1)] for i in range(n + 1)]
		return helper(n, floor)


class Solution:

	def solve(self, n, k, dp):
		if k == 0 or k == 1:
			return k
		if n == 1:
			return k
		if dp[n][k] != -1:
			return dp[n][k]
		count = float('inf')
		for i in range(1, k + 1):
			temp = 1 + max(self.solve(n - 1, i - 1, dp), self.solve(n, k - i, dp))
			count = min(count, temp)
		dp[n][k] = count
		return dp[n][k]

	def eggDrop(self, n, k):
		dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]
		return self.solve(n, k, dp)


class Solution:

	def eggDrop(self, n, k):
		dp = [[1 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if i == 1:
					dp[1][j] = j
				elif i > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = float('inf')
					for e in range(1, j):
						c = 1 + max(dp[i - 1][e - 1], dp[i][j - e])
						if c < dp[i][j]:
							dp[i][j] = c
		return dp[n][k]


class Solution:

	def eggDrop(self, n: int, k: int) -> int:
		dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i][1] = 1
		for j in range(1, k + 1):
			dp[1][j] = j
		for i in range(2, n + 1):
			for j in range(2, k + 1):
				dp[i][j] = float('inf')
				(low, high) = (1, j)
				while low <= high:
					mid = (low + high) // 2
					cost_if_broken = dp[i - 1][mid - 1]
					cost_if_not_broken = dp[i][j - mid]
					cost = max(cost_if_broken, cost_if_not_broken) + 1
					if cost < dp[i][j]:
						dp[i][j] = cost
					if cost_if_broken < cost_if_not_broken:
						low = mid + 1
					else:
						high = mid - 1
		return dp[n][k]


class Solution:

	def eggDrop(self, e, f):
		dp = [[0] * (f + 1) for i in range(e + 1)]
		for i in range(1, f + 1):
			dp[1][i] = i
		for i in range(1, e + 1):
			dp[i][1] = 1
		INT_MAX = 32767
		for i in range(2, e + 1):
			for j in range(2, f + 1):
				dp[i][j] = INT_MAX
				for k in range(1, j + 1):
					res = max(dp[i - 1][k - 1], dp[i][j - k])
					if res < dp[i][j]:
						dp[i][j] = res + 1
		return dp[e][f]


class Solution:

	def eggDrop(self, n, k):
		(m, n) = (n + 1, k + 1)
		dp = [[0 for i in range(n)] for i in range(m)]
		for i in range(1, m):
			for j in range(n):
				if i == 1:
					dp[i][j] = j
				elif j == 0 or j == 1:
					dp[i][j] = j
				else:
					(start, end) = (1, j)
					optimumFloor = start
					while start <= end:
						mid = start + (end - start) // 2
						(left, right) = (dp[i - 1][mid - 1], dp[i][j - mid])
						if left < right:
							start = mid + 1
							optimumFloor = start
						else:
							end = mid - 1
					breaks = 1 + dp[i - 1][optimumFloor - 1]
					notBreaks = 1 + dp[i][j - optimumFloor]
					worstCase = max(breaks, notBreaks)
					dp[i][j] = worstCase
		return dp[m - 1][n - 1]


class Solution:

	def eggDrop(self, n, k):
		(m, n) = (n + 1, k + 1)
		dp = [[0 for i in range(n)] for i in range(m)]
		for i in range(1, m):
			for j in range(n):
				if i == 1:
					dp[i][j] = j
				elif j == 0 or j == 1:
					dp[i][j] = j
				else:
					minMoves = 99999999
					for floor in range(1, j + 1):
						breaks = 1 + dp[i - 1][floor - 1]
						notBreaks = 1 + dp[i][j - floor]
						worstCase = max(breaks, notBreaks)
						minMoves = min(minMoves, worstCase)
					dp[i][j] = minMoves
		return dp[m - 1][n - 1]


class Solution:

	def eggDrop(self, n, k):
		dp = {}

		def fun(e, f):
			if f == 0 or f == 1:
				return f
			if (e, f) in dp:
				return dp[e, f]
			if e == 1:
				return f
			l = float('inf')
			for i in range(1, f + 1):
				l = min(l, 1 + max(fun(e - 1, i - 1), fun(e, f - i)))
			dp[e, f] = l
			return dp[e, f]
		return fun(n, k)


class Solution:

	def solveMem(self, e: int, f: int, dp) -> int:
		if f == 0 or f == 1:
			return f
		if e == 1:
			return f
		if dp[e][f] != -1:
			return dp[e][f]
		mini = float('inf')
		for k in range(1, f + 1):
			breakhua = self.solveMem(e - 1, k - 1, dp)
			breaknahihua = self.solveMem(e, f - k, dp)
			temp = 1 + max(breakhua, breaknahihua)
			mini = min(mini, temp)
			dp[e][f] = mini
		return dp[e][f]

	def eggDrop(self, k, n):
		dp = [[-1 for cols in range(n + 1)] for rows in range(k + 1)]
		return self.solveMem(k, n, dp)


def eggDropUtil(eggs, floors, dp):
	if eggs == 0 or floors == 0:
		return 0
	if eggs == 1:
		return floors
	if floors == 1:
		return 1
	if (eggs, floors) in dp:
		return dp[eggs, floors]
	moves = floors
	for floor in range(1, floors + 1):
		a = 1 + eggDropUtil(eggs - 1, floor - 1, dp)
		b = 1 + eggDropUtil(eggs, floors - floor, dp)
		moves = min(moves, max(a, b))
	dp[eggs, floors] = moves
	return moves

class Solution:

	def eggDrop(self, n, k):
		return eggDropUtil(n, k, {})


class Solution:

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

	def eggDrop(self, n, k):
		if (n, k) in self.memo:
			return self.memo[n, k]
		if n == 1:
			self.memo[n, k] = k
			return k
		if k == 0:
			return 0
		ans = float('inf')
		for i in range(1, k + 1):
			ans = min(ans, max(self.eggDrop(n - 1, i - 1), self.eggDrop(n, k - i)) + 1)
		self.memo[n, k] = ans
		return ans