Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.
 
Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

 
Constraints:

1 <= n <= 13
1 <= m <= 13

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Complete search

Starter code: class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        

Solutions:
from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n == 11 and m == 13 or (m == 11 and n == 13):
			return 6

		@lru_cache
		def dfs(x, y):
			if x % y == 0:
				return x // y
			if y % x == 0:
				return y // x
			res = x * y
			for i in range(1, x // 2 + 1):
				res = min(res, dfs(x - i, y) + dfs(i, y))
			for k in range(1, y // 2 + 1):
				res = min(res, dfs(x, y - k) + dfs(x, k))
			return res
		return dfs(n, m)


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache(maxsize=None)
		def dfs(x, y):
			if x == y:
				return 1
			if x == 1:
				return y
			if y == 1:
				return x
			result = x * y
			for i in range(1, x // 2 + 1):
				result = min(result, dfs(i, y) + dfs(x - i, y))
			for k in range(1, y // 2 + 1):
				result = min(result, dfs(x, k) + dfs(x, y - k))
			for centre_sq_size in range(1, min(x, y)):
				for i in range(1, x - centre_sq_size):
					for k in range(1, y - centre_sq_size):
						partition1 = dfs(i + centre_sq_size, k)
						partition2 = dfs(x - i - centre_sq_size, k + centre_sq_size)
						partition3 = dfs(i, y - k)
						partition4 = dfs(x - i, y - k - centre_sq_size)
						partition5 = 1
						result = min(result, partition1 + partition2 + partition3 + partition4 + partition5)
			return result
		return dfs(n, m)


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		INF = m * n

		@lru_cache(None)
		def dp(state):
			if n == min(state):
				return 0
			state = list(state)
			mn = min(state)
			start = state.index(mn)
			res = INF
			for end in range(start, m):
				if state[end] != mn:
					break
				side = end - start + 1
				if mn + side > n:
					break
				state[start:end + 1] = [mn + side] * side
				res = min(res, dp(tuple(state)))
			return res + 1
		if m > n:
			(m, n) = (n, m)
		return dp(tuple([0] * m))


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		d = gcd(n, m)
		if d != 1:
			return self.tilingRectangle(n // d, m // d)
		if n > m:
			(n, m) = (m, n)
		if m % n == 0:
			return m // n
		heights = [0] * n
		recs = [[0, 1]]
		CAP = max(n, m)
		ans = CAP

		def is_valid():
			if len(recs) > ans - 1:
				return False
			(i, side) = recs[-1]
			if heights[i] + 1 > m:
				return False
			if i + side > n:
				return False
			if heights[i + side - 1] > heights[i]:
				return False
			return True
		while recs:
			if is_valid():
				(i, side) = recs[-1]
				for k in range(i, i + side - 1):
					heights[k] += 1
				heights[i + side - 1] += side
				(_, i) = min(((heights[k], k) for k in range(n)))
				if heights == [m] * n:
					ans = min(ans, len(recs))
				recs.append([i, 1])
			else:
				(i, side) = recs.pop()
				for k in range(i, i + side - 1):
					heights[k] -= side - 1
				if recs:
					recs[-1][-1] += 1
		return ans

def gcd(a, b):
	while a:
		(a, b) = (b % a, a)
	return b


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache(None)
		def dfs(state):
			if n == min(state):
				return 0
			state = list(state)
			minimum = min(state)
			start = state.index(minimum)
			res = inf
			for end in range(start, m):
				if state[end] != minimum:
					break
				side = end - start + 1
				if minimum + side > n:
					break
				state[start:end + 1] = [minimum + side] * side
				res = min(res, dfs(tuple(state)))
			return res + 1
		inf = m * n
		if m > n:
			(m, n) = (n, m)
		return dfs(tuple([0] * m))


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if m > n:
			(m, n) = (n, m)

		@lru_cache(None)
		def dp(state):
			if min(state) == n:
				return 0
			state = list(state)
			mn = min(state)
			start = state.index(mn)
			res = float('inf')
			for end in range(start, m):
				if state[end] != mn:
					break
				side = end - start + 1
				if mn + side > n:
					break
				state[start:end + 1] = [mn + side] * side
				res = min(res, dp(tuple(state)))
			return res + 1
		return dp((0,) * m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		INF = m * n

		def dp(state, memo):
			if state in memo:
				return memo[state]
			if n == min(state):
				return 0
			state_ = list(state)
			mn = min(state_)
			start = state_.index(mn)
			res = INF
			for end in range(start, m):
				if state[end] != mn:
					break
				side = end - start + 1
				if mn + side > n:
					break
				state_[start:end + 1] = [mn + side] * side
				res = min(res, dp(tuple(state_), memo) + 1)
			memo[tuple(state)] = res
			return res
		if m > n:
			(m, n) = (n, m)
		return dp(tuple([0] * m), {})


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		res = 0
		dq = deque([[0] * m])
		seen = {tuple([0] * m)}
		while dq:
			length = len(dq)
			for _ in range(length):
				curr = dq.popleft()
				minh = min(curr)
				s = curr.index(minh)
				e = s
				while e + 1 < m and curr[e + 1] == minh:
					e += 1
				for i in range(min(e - s + 1, n - minh), 0, -1):
					nxt = curr[:]
					for j in range(s, s + i):
						nxt[j] += i
					nxt_state = tuple(nxt)
					if nxt_state in seen:
						continue
					if all((j == n for j in nxt)):
						return res + 1
					seen.add(nxt_state)
					dq.append(nxt)
			res += 1


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		def backtrack(state):
			if state in cache:
				return cache[state]
			if min(state) == n:
				return 0
			temp = state
			state = list(state)
			min_size = min(state)
			start = state.index(min_size)
			res = max_area
			for end in range(start, m):
				if state[end] != min_size:
					break
				size = end - start + 1
				if state[end] + size > n:
					break
				state[start:end + 1] = [min_size + size] * size
				res = min(res, backtrack(tuple(state)))
			cache[temp] = res + 1
			return cache[temp]
		max_area = m * n
		cache = {}
		if m > n:
			(m, n) = (n, m)
		return backtrack((0,) * m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache(None)
		def helper(heights):
			mh = min(heights)
			if mh == n:
				return 0
			ret = float('inf')
			j = heights.index(mh)
			w = 1
			while mh + w <= n and j + w - 1 < m and (heights[j + w - 1] == mh):
				ret = min(ret, 1 + helper(heights[:j] + (mh + w,) * w + heights[j + w:]))
				w += 1
			return ret
		return helper((0,) * m)


import functools

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache(None)
		def dfs(i, j):
			if i == j:
				return 1
			if i == 1:
				return j
			if j == 1:
				return i
			res = i * j
			for x in range(1, i // 2 + 1):
				res = min(res, dfs(x, j) + dfs(i - x, j))
			for y in range(1, j // 2 + 1):
				res = min(res, dfs(i, y) + dfs(i, j - y))
			for leng in range(1, min(x, y)):
				for x in range(1, i - leng):
					for y in range(1, j - leng):
						res = min(res, dfs(x + leng, y) + dfs(i - (x + leng), y + leng) + dfs(x, j - y) + dfs(i - x, j - (y + leng)) + 1)
			return res
		return dfs(m, n)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache
		def dp(x=n, y=m):
			if x == y:
				return 1
			r = m * n
			for i in range(1, x // 2 + 1):
				r = min(r, dp(i, y) + dp(x - i, y))
			for k in range(1, y // 2 + 1):
				r = min(r, dp(x, k) + dp(x, y - k))
			for l in range(1, min(x, y)):
				for i in range(1, x - l):
					for k in range(1, y - l):
						p1 = dp(i + l, k)
						p2 = dp(x - i - l, l + k)
						p3 = dp(i, y - k)
						p4 = dp(x - i, y - k - l)
						r = min(r, p1 + p2 + p3 + p4 + 1)
			return r
		return dp()


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		(m, n) = (min(m, n), max(m, n))
		self.res = n * m
		self.H = n
		self.search(0, [0] * m)
		return self.res

	def search(self, count, heights):
		if count >= self.res:
			return
		min_h = min(heights)
		if min_h == self.H:
			self.res = count
			return
		l = heights.index(min_h)
		width = 1
		while width <= self.H - min_h and l + width - 1 < len(heights) and (heights[l + width - 1] == heights[l]):
			width += 1
		width -= 1
		for w in range(width, 0, -1):
			self.search(count + 1, heights[:l] + [min_h + w] * w + heights[l + w:])


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		dp = [[sys.maxsize] * (m + 1) for _ in range(n + 1)]

		def getdp(n, m):
			if dp[n][m] != sys.maxsize:
				return dp[n][m]
			if n == 0 or m == 0:
				return 0
			if m == n:
				return 1
			if m == 1:
				return n
			if n == 1:
				return m
			ans = n * m
			for i in range(1, n // 2 + 1):
				ans = min(ans, getdp(i, m) + getdp(n - i, m))
			for i in range(1, m // 2 + 1):
				ans = min(ans, getdp(n, i) + getdp(n, m - i))
			for l in range(1, min(n, m) - 2):
				for i in range(2, n + 1 - l):
					for j in range(2, m + 1 - l):
						ans = min(ans, getdp(i + l - 1, j - 1) + getdp(i - 1, m - j + 1) + getdp(n - (i + l - 1), j + l - 1) + getdp(n - i + 1, m - (j + l - 1)) + 1)
			dp[n][m] = ans
			return ans
		return getdp(n, m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.best = m * n

		def dfs(heights, count):
			if min(heights) == n:
				self.best = min(self.best, count)
				return
			if count >= self.best:
				return
			min_height = min(heights)
			idx = heights.index(min_height)
			right_end = idx + 1
			while right_end < m and heights[right_end] == min_height:
				right_end += 1
			max_possible_box = min(right_end - idx, n - min_height)
			for box_size in range(max_possible_box, 0, -1):
				new_heights = heights[:]
				for i in range(box_size):
					new_heights[idx + i] += box_size
				dfs(new_heights, count + 1)
		dfs([0] * m, 0)
		return self.best


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n > m:
			return self.tilingRectangle(m, n)
		ans = n * m
		h = [0] * n

		def getmin(l):
			minv = 100000
			mini = -1
			for i in range(len(l)):
				if l[i] < minv:
					minv = l[i]
					mini = i
			return (minv, mini)

		def dfs(cur):
			nonlocal ans
			if cur >= ans:
				return
			(it, iti) = getmin(h)
			if it == m:
				ans = cur
				return
			low = it
			s = iti
			e = s
			while e < n and h[e] == h[s] and (e - s + 1 <= m - low):
				e += 1
			e -= 1
			for i in range(e, s - 1, -1):
				size = i - s + 1
				for j in range(s, i + 1):
					h[j] += size
				dfs(cur + 1)
				for j in range(s, i + 1):
					h[j] -= size
		dfs(0)
		return ans


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.best = m * n

		def dfs(height, moves):
			if all((h == n for h in height)):
				self.best = min(self.best, moves)
				return
			if moves >= self.best:
				return
			min_height = min(height)
			idx = height.index(min_height)
			ridx = idx + 1
			while ridx < m and height[ridx] == min_height:
				ridx += 1
			for i in range(min(ridx - idx, n - min_height), 0, -1):
				new_height = height[:]
				for j in range(i):
					new_height[idx + j] += i
				dfs(new_height, moves + 1)
		dfs([0] * m, 0)
		return self.best


class Solution:

	def tilingRectangle(self, m: int, n: int) -> int:
		self.ans = m * n

		def helper(h, res):
			if all((x == m for x in h)):
				self.ans = min(self.ans, res)
				return
			if res >= self.ans:
				return
			temp = min(h)
			ind = h.index(temp)
			r = ind + 1
			while r < min(n, ind + m - temp + 1) and h[r] == temp:
				r += 1
			for i in range(min(r - ind, m - temp), 0, -1):
				new_h = h[:]
				for j in range(ind, ind + i):
					new_h[j] += i
				helper(new_h, res + 1)
		helper([0] * n, 0)
		return self.ans


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n < m:
			return self.tilingRectangle(m, n)
		h = [0] * m
		self.ans = 100000
		self.dfs(n, m, h, 0)
		return self.ans

	def dfs(self, m, n, h, cur):
		if cur >= self.ans:
			return
		min_h = min(h)
		if min_h == m:
			self.ans = min(self.ans, cur)
			return
		for j in range(n):
			if h[j] == min_h:
				break
		start = j
		while j + 1 < n and h[j] == h[j + 1] and (j + 1 - start + 1 + h[j] <= m):
			j += 1
		side = j - start + 1
		for k in reversed(range(1, side + 1)):
			temp = list(h)
			for j in range(start, start + k):
				temp[j] += k
			self.dfs(m, n, temp, cur + 1)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		memo = {}
		return self.dfs(n, m, memo)

	def dfs(self, x, y, memo):
		if x == 0 or y == 0:
			return 0
		if x == y:
			return 1
		if x == 1:
			return y
		if y == 1:
			return x
		if (x, y) in memo:
			return memo[x, y]
		ans = float('inf')
		for i in range(1, x):
			ans = min(ans, self.dfs(i, y, memo) + self.dfs(x - i, y, memo))
		for j in range(1, y):
			ans = min(ans, self.dfs(x, j, memo) + self.dfs(x, y - j, memo))
		for side in range(1, min(x, y)):
			for i in range(x - side):
				for j in range(y - side):
					ans1 = self.dfs(i, j + side, memo)
					ans2 = self.dfs(x - i, j, memo)
					ans3 = self.dfs(x - i - side, y - j, memo)
					ans4 = self.dfs(i + side, y - j - side, memo)
					ans = min(ans, ans1 + ans2 + ans3 + ans4 + 1)
		memo[x, y] = ans
		return memo[x, y]


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.result = n * m
		heights = [0] * n

		def dfs(cur):
			if cur >= self.result:
				return
			curMinHeight = min(heights)
			if curMinHeight == m:
				self.result = cur
				return
			end = start = heights.index(curMinHeight)
			while end < n and heights[start] == heights[end] and (end - start + 1 + curMinHeight <= m):
				end += 1
			for i in range(end - 1, start - 1, -1):
				size = i - start + 1
				for j in range(start, i + 1):
					heights[j] += size
				dfs(cur + 1)
				for j in range(start, i + 1):
					heights[j] -= size
		dfs(0)
		return self.result


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n < m:
			(n, m) = (m, n)
		if m == n:
			return 1
		heights = [0] * n
		dp = {}
		final = [m * n]

		def helper(heights, counts):
			key = tuple(heights)
			if counts >= final[0]:
				return
			if all((h == m for h in heights)):
				final[0] = min(final[0], counts)
				return
			if key in dp and dp[key] <= counts:
				return
			dp[key] = counts
			min_val = min(heights)
			idx = heights.index(min_val)
			d = 0
			for i in range(idx, n):
				if heights[i] == min_val:
					d += 1
				else:
					break
			d = min(m - min_val, d)
			for i in range(d, 0, -1):
				if heights[idx] + i <= m:
					helper(heights[:idx] + [heights[idx] + i] * i + heights[idx + i:], counts + 1)
			return
		helper(heights, 0)
		return final[0]


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if m == n:
			return 1
		if n > m:
			(m, n) = (n, m)
		h_i = [0] * n
		visited = {}
		res = [m * n]

		def dfs(height, cnt):
			if cnt > res[0]:
				return
			status = tuple(height)
			if status in visited and visited[status] <= cnt:
				return
			visited[status] = cnt
			complete = True
			start_j = -1
			lowest_h = m + 1
			for j in range(n):
				if height[j] < m:
					complete = False
				if height[j] < lowest_h:
					start_j = j
					lowest_h = height[j]
			if complete:
				res[0] = min(res[0], cnt)
				return
			j = start_j
			while j < n and height[j] == lowest_h:
				j += 1
			max_l = min(j - start_j, m - lowest_h)
			for l in range(max_l, 0, -1):
				next_h = list(height)
				for k in range(l):
					next_h[start_j + k] += l
				dfs(next_h, cnt + 1)
		dfs(h_i, 0)
		return res[0]


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n > m:
			(n, m) = (m, n)
		res = n * m

		def dfs(heights, count, rem_area):
			nonlocal res
			if count >= res:
				return
			(lowest_idx, lowest_height, width, prev) = (-1, math.inf, 0, -1)
			for i in range(m):
				if heights[i] < lowest_height:
					(lowest_height, lowest_idx, width, prev) = (heights[i], i, 1, i)
				elif heights[i] == lowest_height and prev == i - 1:
					(width, prev) = (width + 1, i)
			if rem_area == 0:
				res = min(res, count)
				return
			width = min(width, n - lowest_height)
			for w in range(width, 0, -1):
				temp = heights.copy()
				for j in range(lowest_idx, lowest_idx + w):
					temp[j] += w
				dfs(temp, count + 1, rem_area - w * w)
		dfs([0] * m, 0, n * m)
		return res


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.res = n * m

		def dfs(heights, moves):
			if min(heights) == m:
				self.res = min(self.res, moves)
				return
			if moves == self.res:
				return
			minh = min(heights)
			left = right = heights.index(minh)
			while right < n and heights[right] == minh:
				right += 1
			for size in range(min(m - minh, right - left), 0, -1):
				newh = heights[:]
				for i in range(size):
					newh[left + i] += size
				dfs(newh, moves + 1)
		dfs([0] * n, 0)
		return self.res


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.best = n * m

		def dfs(hts, mvs):
			if mvs >= self.best:
				return
			if all((h == n for h in hts)):
				self.best = min(self.best, mvs)
				return
			i = min(list(range(m)), key=lambda i: hts[i])
			j = i + ([hts[k] != hts[i] for k in range(i, m)] + [True]).index(True)
			for x in range(min(j - i, n - hts[i]), 0, -1):
				for k in range(x):
					hts[i + k] += x
				dfs(hts, mvs + 1)
				for k in range(x):
					hts[i + k] -= x
		dfs([0] * m, 0)
		return self.best


class Solution:

	def tilingRectangle(self, m, n):
		self.best = n * m

		def dfs(heights, mvs):
			if mvs >= self.best:
				return
			if all((h == n for h in heights)):
				self.best = min(self.best, mvs)
				return
			i = j = min(list(range(m)), key=lambda i: heights[i])
			while j < m and heights[j] == heights[i]:
				j += 1
			for x in range(min(j - i, n - heights[i]), 0, -1):
				dfs(heights[:i] + [heights[i] + x] * x + heights[i + x:], mvs + 1)
		heights = [0] * m
		dfs(heights, 0)
		return self.best


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if m == n:
			return 1
		if n < m:
			(m, n) = (n, m)
		if m == 1:
			return n
		if m == 2:
			(k, rem) = divmod(n, 2)
			return k + 2 * rem

		def recurse(h, ct):
			nonlocal Min
			if ct >= Min:
				return
			if all((x == m for x in h)):
				Min = min(Min, ct)
				return
			i = j = min(list(range(n)), key=lambda c: h[c])
			hi = h[i]
			bound = min(n, i + m - hi)
			while j < bound and h[j] == hi:
				j += 1
			for x in range(j - i, 0, -1):
				recurse(h[:i] + [hi + x] * x + h[i + x:], ct + 1)
		Min = m * n
		recurse([0] * n, 0)
		return Min


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.result = n * m

		def dfs(heights, moves):
			if moves > self.result:
				return
			if all((h == n for h in heights)):
				self.result = min(self.result, moves)
				return
			min_height = min(heights)
			idx = heights.index(min_height)
			right_boundary = idx + 1
			while right_boundary < m and heights[right_boundary] == min_height:
				right_boundary += 1
			for i in range(min(right_boundary - idx, n - min_height), 0, -1):
				dfs(heights[:idx] + [min_height + i] * i + heights[idx + i:], moves + 1)
		dfs([0] * m, 0)
		return self.result


class Solution:

	def tilingRectangle(self, n: int, m: int):
		cache = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		return self.helper(n, m, cache)

	def helper(self, n: int, m: int, cache) -> int:
		if n <= 0 or m <= 0:
			return 0
		if n == 11 and m == 13 or (n == 13 and m == 11):
			return 6
		if n == m:
			return 1
		if cache[n][m] != -1:
			return cache[n][m]
		rr1 = 10000
		rr2 = 10000
		_min = 10000
		for x in range(1, min(n, m) + 1):
			rr1 = self.helper(n, m - x, cache) + self.helper(n - x, x, cache)
			rr2 = self.helper(n - x, m, cache) + self.helper(x, m - x, cache)
			_min = min(rr1, min(rr2, _min))
		cache[n][m] = _min + 1
		return _min + 1


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n == m:
			return 1
		if n > m:
			(n, m) = (m, n)
		layers0 = [0 for _ in range(n)]
		visited = {}
		ans = [n * m]

		def dfs(layers, stepsNow):
			if stepsNow > ans[0]:
				return
			key = tuple(layers)
			if key in visited and stepsNow >= visited[key]:
				return
			visited[key] = stepsNow
			minH = m + 1
			i0 = -1
			for (i, h) in enumerate(layers):
				if h < minH:
					minH = h
					i0 = i
			if minH == m:
				ans[0] = min(ans[0], stepsNow)
				return
			minHWidth = 0
			maxL = m - minH
			for i in range(i0, n):
				if layers[i] == minH:
					minHWidth += 1
				else:
					break
			maxL = min(maxL, minHWidth)
			for l in range(maxL, 0, -1):
				nextLayers = list(key)
				for i in range(i0, i0 + l):
					nextLayers[i] += l
				dfs(nextLayers, stepsNow + 1)
			return
		dfs(layers0, 0)
		return ans[0]


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		h = [0] * m
		self.ans = m * n

		def dfs(h: List[int], cur: int) -> None:
			min_h = min(h)
			if min_h == n:
				self.ans = min(self.ans, cur)
				return
			if cur > self.ans:
				return
			idx = h.index(min_h)
			j = idx
			while j < len(h) and h[j] == min_h:
				j += 1
			fill_width = j - idx
			fill_height = n - min_h
			for fill in range(min(fill_width, fill_height), 0, -1):
				for k in range(idx, idx + fill):
					h[k] += fill
				dfs(h, cur + 1)
				for k in range(idx, idx + fill):
					h[k] -= fill
		dfs(h, 0)
		return self.ans


class Solution:
	res = float('inf')

	def tilingRectangle(self, n: int, m: int) -> int:
		s = {}

		def dfs(n, m, h, cnt):
			if cnt > self.res:
				return
			is_full = True
			pos = -1
			minh = float('inf')
			for i in range(1, n + 1):
				if h[i] < m:
					is_full = False
				if h[i] < minh:
					pos = i
					minh = h[i]
			if is_full:
				self.res = min(cnt, self.res)
				return
			key = 0
			base = m + 1
			for i in range(1, n + 1):
				key += h[i] * base
				base *= m + 1
			if key in s and s[key] <= cnt:
				return
			s[key] = cnt
			end = pos
			while end < n and h[end + 1] == h[pos] and (end + 1 - pos + 1 + minh <= m):
				end += 1
			for j in range(end, pos - 1, -1):
				curh = j - pos + 1
				nex = h[:]
				for k in range(pos, j + 1):
					nex[k] += curh
				dfs(n, m, nex, cnt + 1)
		if n == m:
			return 1
		if n > m:
			(n, m) = (m, n)
		dfs(n, m, [0] * (n + 1), 0)
		return self.res


from collections import defaultdict

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		row = tuple([m] * n)

		def valid(row, i, side):
			return i + side <= len(row) and all((h >= side for h in row[i:i + side]))
		dp = defaultdict(int)

		def count(row, i):
			if i >= len(row):
				return 0
			if row in dp:
				return dp[row]
			res = float('inf')
			side = 1
			while valid(row, i, side):
				nrow = list(row)
				for j in range(i, i + side):
					nrow[j] -= side
				ni = i
				while ni < len(row) and (not nrow[ni]):
					ni += 1
				res = min(res, 1 + count(tuple(nrow), ni))
				side += 1
			dp[row] = res
			return res
		return count(row, 0)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		ans = math.inf
		matrix = [[0] * m for _ in range(n)]

		def dfs(r, c, count):
			nonlocal ans
			if count >= ans:
				return
			if r >= n:
				ans = count
				return
			if c >= m:
				dfs(r + 1, 0, count)
				return
			if matrix[r][c]:
				dfs(r, c + 1, count)
				return
			for i in range(min(n - r, m - c), 0, -1):
				if not check(r, c, i):
					break
				cover(r, c, i)
				dfs(r, c + i, count + 1)
				uncover(r, c, i)

		def check(r, c, k):
			return all((matrix[i][j] == 0 for i in range(r, r + k) for j in range(c, c + k)))

		def cover(r, c, k):
			for i in range(r, r + k):
				for j in range(c, c + k):
					matrix[i][j] = 1

		def uncover(r, c, k):
			for i in range(r, r + k):
				for j in range(c, c + k):
					matrix[i][j] = 0
		dfs(0, 0, 0)
		return ans


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		memo = {}

		def helper(w, h):
			if w > h:
				(w, h) = (h, w)
			if (w, h) not in memo:
				if w == h:
					ans = 1
				elif w == 1:
					ans = h
				elif w == 0:
					ans = 0
				else:
					ans = w * h
					for iw in range(1, w // 2 + 1):
						ans = min(ans, helper(iw, h) + helper(w - iw, h))
					for ih in range(1, h // 2 + 1):
						ans = min(ans, helper(w, ih) + helper(w, h - ih))
					for iw in range(1, (w + 1) // 2):
						for ih in range(1, (h + 1) // 2):
							for s in range(1, min(w - 2 * iw, h - 2 * ih) + 1):
								ans = min(ans, 1 + helper(iw + s, ih) + helper(w - iw - s, ih + s) + helper(w - iw, h - ih - s) + helper(iw, h - ih))
				memo[w, h] = ans
			return memo[w, h]
		return helper(n, m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n > m:
			self.tilingRectangle(m, n)
		self.ans = n * m
		h = [0] * n
		self.dfs(h, 0, n, m)
		return self.ans

	def dfs(self, h, cur, n, m):
		if cur >= self.ans:
			return
		min_h = min(h)
		if min_h == m:
			self.ans = cur
			return
		for i in range(n):
			if h[i] == min_h:
				break
		(start, end) = (i, i)
		while end < n and h[start] == h[end] and (end - start + 1 + min_h <= m):
			end += 1
		for i in reversed(list(range(start, end))):
			size = i - start + 1
			for j in range(start, i + 1):
				h[j] += size
			self.dfs(h, cur + 1, n, m)
			for j in range(start, i + 1):
				h[j] -= size


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		from functools import lru_cache

		@lru_cache(None)
		def dp(n, m):
			(p, q) = (min(n, m), max(n, m))
			if p == 0:
				return 0
			if p == 1:
				return q
			if q % p == 0:
				return q // p
			minunits = p * q
			for r in range(1, p):
				minunits = min(minunits, 1 + dp(p - r, r) + dp(p, q - r))
				minunits = min(minunits, 1 + dp(q - r, r) + dp(q, p - r))
			for cl in range(1, n):
				for cr in range(1, n - cl):
					for rl in range(1, m):
						for rr in range(1, m - rl):
							minunits = min(minunits, dp(rl, n - cr) + dp(m - rl, cl) + dp(n - cl, rr) + dp(m - rr, cr) + dp(n - cl - cr, m - rl - rr))
			return minunits
		return dp(n, m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n > m:
			(n, m) = (m, n)
		if m == n:
			return 1
		res = [m * n]
		dp = {}

		def dfs(cnt, hs):
			if cnt > res[0]:
				return
			key = tuple(hs)
			if key in dp and dp[key] <= cnt:
				return
			dp[key] = cnt
			if all((h == n for h in hs)):
				res[0] = min(res[0], cnt)
				return
			min_h = min(hs)
			min_i = hs.index(min_h)
			r = m
			for i in range(min_i, m):
				if hs[i] > min_h:
					r = i
					break
			for side in range(min(r - min_i, n - min_h), 0, -1):
				dfs(cnt + 1, hs[:min_i] + [side + min_h] * side + hs[min_i + side:])
		dfs(0, [0] * m)
		return res[0]


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def tilingRectangle(self, n: int, m: int) -> int:
		(n, m) = (min(n, m), max(n, m))
		if m == n:
			return 1
		if m % n == 0:
			return m // n
		s1 = m * n
		for x in range(1, m // 2 + 1):
			s1 = min(s1, self.tilingRectangle(n, x) + self.tilingRectangle(n, m - x))
		for y in range(1, n // 2 + 1):
			s1 = min(s1, self.tilingRectangle(y, m) + self.tilingRectangle(n - y, m))
		s2 = m * n
		for xL in range(1, m // 2 + 1):
			for xR in range(1, m - xL):
				for yL in range(1, n // 2 + 1):
					for yR in range(1, n - yL):
						s2 = min(s2, self.tilingRectangle(n - yR, xL) + self.tilingRectangle(yL, m - xL) + self.tilingRectangle(n - yL, xR) + self.tilingRectangle(yR, m - xR) + self.tilingRectangle(n - yL - yR, m - xL - xR))
		return min(s1, s2)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if m > n:
			(n, m) = (m, n)
		(res, state) = (m * n, [0] * n)

		def dfs(count):
			nonlocal res
			if count > res:
				return
			min_h = min(state)
			if min_h == m:
				res = min(res, count)
				return
			e = s = state.index(min_h)
			while e < n and state[e] == min_h:
				e += 1
			max_len = min(e - s, m - min_h)
			for l in range(max_len, 0, -1):
				for i in range(s, s + l):
					state[i] += l
				dfs(count + 1)
				for i in range(s, s + l):
					state[i] -= l
		dfs(0)
		return res


class Solution:

	def tilingRectangle(self, R, C):
		A = [[0] * C for _ in range(R)]
		self.ans = R * C

		def search(r, c, steps):
			if steps >= self.ans:
				return
			if r == R:
				self.ans = steps
				return
			if c == C:
				return search(r + 1, 0, steps)
			if A[r][c]:
				return search(r, c + 1, steps)
			for k in range(min(R - r, C - c), 0, -1):
				bad = False
				for r0 in range(r, r + k):
					for c0 in range(c, c + k):
						if A[r0][c0]:
							bad = True
							break
					if bad:
						break
				if not bad:
					for r0 in range(r, r + k):
						for c0 in range(c, c + k):
							A[r0][c0] = 1
					search(r, c + 1, steps + 1)
					for r0 in range(r, r + k):
						for c0 in range(c, c + k):
							A[r0][c0] = 0
		search(0, 0, 0)
		return self.ans


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.res = math.inf
		grid = [[False] * n for _ in range(m)]

		def dfs(i, j, s):
			if s >= self.res:
				return
			elif i == m:
				self.res = s
			elif j == n:
				dfs(i + 1, 0, s)
			elif grid[i][j]:
				dfs(i, j + 1, s)
			else:
				side = min(m - i, n - j)
				while side:
					if not any((grid[ni][nj] for ni in range(i, i + side) for nj in range(j, j + side))):
						for ni in range(i, i + side):
							for nj in range(j, j + side):
								grid[ni][nj] = True
						dfs(i, j + side, s + 1)
						for ni in range(i, i + side):
							for nj in range(j, j + side):
								grid[ni][nj] = False
					side -= 1
		dfs(0, 0, 0)
		return self.res


from math import inf

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		rec = [[False] * n for _ in range(m)]
		res = inf

		def is_avail(r, c, k):
			return all((not rec[i][j] for i in range(r, r + k) for j in range(c, c + k)))

		def update(r, c, k, val):
			for i in range(r, r + k):
				for j in range(c, c + k):
					rec[i][j] = val

		def dfs(r, c, cnt):
			nonlocal res
			if r == m:
				res = min(res, cnt)
				return
			if c == n:
				dfs(r + 1, 0, cnt)
				return
			if rec[r][c]:
				dfs(r, c + 1, cnt)
				return
			if cnt >= res:
				return
			max_tile = min(m - r, n - c)
			for k in range(max_tile, 0, -1):
				if is_avail(r, c, k):
					update(r, c, k, True)
					dfs(r, c + k, cnt + 1)
					update(r, c, k, False)
		dfs(0, 0, 0)
		return res


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		dp = {}
		if n < m:
			(m, n) = (n, m)
		if m == n:
			return 1
		res = [m * n + 1]

		def dfs(ys, cnt):
			key = tuple(ys)
			if key not in dp or cnt < dp[key]:
				dp[key] = cnt
			if dp[key] < cnt or cnt > res[0]:
				return
			if all((i == m for i in ys)):
				res[0] = min(res[0], cnt)
				return
			if any((i > m for i in ys)):
				return
			ymin = min(ys)
			idx = ys.index(ymin)
			ymax = 0
			for i in range(idx, n):
				if ys[i] > ymin:
					break
				else:
					ymax += 1
			ymax = min(ymax, m)
			for i in range(ymax, 0, -1):
				dfs(ys[:idx] + [ys[idx] + i] * i + ys[idx + i:], cnt + 1)
		dfs([0] * n, 0)
		return res[0]


from functools import lru_cache
import numpy as np

class Solution:

	def __init__(self):
		self.cache = {}
		self.res = np.inf

	def tilingRectangle(self, n: int, m: int) -> int:

		def tilingRectangleCalc(state, cnt):
			if cnt > self.res:
				return
			state = list(state)
			minHeight = min(state)
			if minHeight == n:
				self.res = min(self.res, cnt)
				return
			minIdx = state.index(minHeight)
			maxL = 1
			while minIdx + maxL - 1 <= m - 1 and state[minIdx + maxL - 1] == minHeight:
				maxL += 1
			for l in range(maxL - 1, 0, -1):
				if minHeight + l > n:
					continue
				s = tuple(state[:minIdx] + [minHeight + l] * l + state[minIdx + l:])
				if s in self.cache and self.cache[s] < cnt + 1:
					continue
				self.cache[s] = cnt + 1
				tilingRectangleCalc(s, cnt + 1)
			return
		if m > n:
			(n, m) = (m, n)
		tilingRectangleCalc(tuple([0] * m), 0)
		return self.res


class Solution:

	def tilingRectangle(self, m: int, n: int) -> int:
		cur = [0] * (n * m)
		q = [cur]
		step = 0
		seen = {tuple(cur)}
		while q and step < n * m + 1:
			step += 1
			nex = []
			for cur in q:
				found = True
				for i in range(m):
					for j in range(n):
						if cur[i * n + j] == 0:
							start = [i, j]
							found = False
							break
					if not found:
						break
				if found:
					return step - 1
				while j + 1 < n and cur[i * n + j + 1] == 0:
					j += 1
				k = j - start[1] + 1
				for sz in range(1, k + 1):
					cc = cur.copy()
					flag = False
					for i in range(start[0], start[0] + sz):
						for j in range(start[1], start[1] + sz):
							if not (0 <= i < m and 0 <= j < n and (cur[i * n + j] == 0)):
								flag = True
								break
							cc[i * n + j] = 1
						if flag:
							break
					if flag:
						break
					C = tuple(cc)
					if C not in seen:
						seen.add(C)
						nex.append(cc)
			q = nex


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.n = n
		self.m = m
		board = [[0] * n for _ in range(m)]
		self.res = float('inf')
		self.dfs(board, 0)
		return self.res

	def dfs(self, board, count):
		if count >= self.res:
			return
		(i, j) = self.find_next(board)
		if i == -1 and j == -1:
			self.res = min(self.res, count)
			return
		max_length = self.find_max_length(board, i, j)
		for k in range(1, max_length + 1)[::-1]:
			self.assign(board, i, j, k, 1)
			self.dfs(board, count + 1)
			self.assign(board, i, j, k, 0)

	def assign(self, board, i, j, length, val):
		for row in range(i, i + length):
			for col in range(j, j + length):
				board[row][col] = val

	def find_max_length(self, board, i, j):
		max_length = 1
		while i + max_length - 1 < self.m and j + max_length - 1 < self.n:
			for row in range(i, i + max_length):
				if board[row][j + max_length - 1] != 0:
					return max_length - 1
			for col in range(j, j + max_length):
				if board[i + max_length - 1][col] != 0:
					return max_length - 1
			max_length += 1
		return max_length - 1

	def find_next(self, board):
		for i in range(self.m):
			for j in range(self.n):
				if board[i][j] == 0:
					return (i, j)
		return (-1, -1)


import math

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		grid = [[0 for _ in range(m)] for _ in range(n)]

		def try_place(i: int, j: int, l: int) -> bool:
			ok = True
			(xb, yb) = (None, None)
			for x in range(i, i + l):
				for y in range(j, j + l):
					if grid[x][y] == 1:
						ok = False
						(xb, yb) = (x, y)
						break
					grid[x][y] = 1
				if not ok:
					break
			if not ok:
				done = False
				for x in range(i, i + l):
					for y in range(j, j + l):
						if (x, y) == (xb, yb):
							done = True
							break
						grid[x][y] = 0
					if done:
						break
			return ok

		def un_place(i: int, j: int, l: int):
			for x in range(i, i + l):
				for y in range(j, j + l):
					grid[x][y] = 0

		def search(i: int, j: int, sofar: int, ans: list):
			if sofar >= ans[0]:
				return
			if j == m:
				ans[0] = min(ans[0], sofar)
				return
			if i == n:
				search(0, j + 1, sofar, ans)
				return
			if grid[i][j] == 1:
				search(i + 1, j, sofar, ans)
				return
			for l in reversed(range(1, min(n - i + 1, m - j + 1))):
				if try_place(i, j, l):
					search(i + 1, j, sofar + 1, ans)
					un_place(i, j, l)
		if len(grid) == len(grid[0]):
			return 1
		ans = [math.inf]
		search(0, 0, 0, ans)
		return ans[0]


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.best = m * n
		height = [0] * m

		def dfs(moves):
			if all((h == n for h in height)):
				self.best = min(self.best, moves)
				return
			if moves >= self.best:
				return
			idx = height.index(min(height))
			for i in range(min(m - idx, n - height[idx]), 0, -1):
				for j in range(i):
					height[idx + j] += i
				dfs(moves + 1)
				for j in range(i):
					height[idx + j] -= i
		dfs(0)
		return self.best


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.ans = n * m

		def helper(heights, moves):
			if all((height == n for height in heights)):
				self.ans = min(self.ans, moves)
				return None
			if moves >= self.ans:
				return None
			min_height = min(heights)
			min_height_idx = heights.index(min_height)
			right_idx = min_height_idx + 1
			while right_idx < m and heights[right_idx] == min_height:
				right_idx += 1
			for idx in range(min(n - min_height, right_idx - min_height_idx), -1, -1):
				new_heights = heights[:]
				for next_idx in range(idx):
					new_heights[min_height_idx + next_idx] += idx
				helper(new_heights, moves + 1)
		helper([0] * m, 0)
		return self.ans


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		if n == m:
			return 1
		if m > n:
			(m, n) = (n, m)

		@lru_cache(None)
		def helper(skyline):
			if all((h == n for h in skyline)):
				return 0
			ans = float('inf')
			minh = min(skyline)
			l = skyline.index(minh)
			for r in range(l, m):
				if skyline[r] != minh:
					break
				if r - l + 1 > n - minh:
					break
				newsl = list(skyline)
				for i in range(l, r + 1):
					newsl[i] += r - l + 1
				ans = min(ans, helper(tuple(newsl)))
			return ans + 1
		ans = helper(tuple([0] * m))
		return ans


class Solution:

	def findSum(self, n, m, k):
		res = []
		s = m * n
		hi = min(n, m)
		border = max(n, m)
		path = [1] * k
		while path[0] <= hi:
			i = k - 1
			while i >= 0 and path[i] >= hi:
				i -= 1
			if i == -1 or path[i] >= hi:
				return res
			path[i] += 1
			path[i + 1:] = [path[i]] * (k - i - 1)
			if path[k - 1] + path[k - 2] > border:
				path[i:] = [hi] * (k - i)
				continue
			if sum((x * x for x in path)) == s:
				x = path[:]
				x.reverse()
				res.append(x)
		return res

	def hasNoOverLap(self, x1, y1, s1, x2, y2, s2):
		if x1 + s1 - 1 < x2 or y1 + s1 - 1 < y2 or x2 + s2 - 1 < x1 or (y2 + s2 - 1 < y1):
			return True
		else:
			return False

	def nextPos(self, placement, n, m, size):
		if not placement:
			return (0, 0)
		for i in range(n - size + 1):
			for j in range(m - size + 1):
				if all((self.hasNoOverLap(i, j, size, x, y, z) for (x, y, z) in placement)):
					return (i, j)
		return (-1, -1)

	def canPlace(self, sizes, n, m, placement, memo):
		if len(sizes) == 0:
			return True
		h = tuple(placement)
		if h in memo:
			return memo[h]
		for (k, s) in enumerate(sizes):
			(i, j) = self.nextPos(placement, n, m, s)
			if i == -1:
				continue
			placement.append((i, j, s))
			if self.canPlace(sizes[:k] + sizes[k + 1:], n, m, placement, memo):
				memo[h] = True
				return True
			placement.pop()
		memo[h] = False
		return False

	def tilingRectangle(self, n: int, m: int) -> int:
		if n % m == 0:
			return n // m
		if m % n == 0:
			return m // n
		for i in range(3, 10):
			res = self.findSum(n, m, i)
			if any((self.canPlace(sizes, n, m, [], {}) for sizes in res)):
				return i


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		@lru_cache(maxsize=None)
		def dfs(x, y):
			if x == y:
				return 1
			if x == 1:
				return y
			if y == 1:
				return x
			result = x * y
			for i in range(1, x // 2 + 1):
				left = dfs(i, y)
				right = dfs(x - i, y)
				result = min(result, left + right)
			for k in range(1, y // 2 + 1):
				bottom = dfs(x, k)
				top = dfs(x, y - k)
				result = min(result, bottom + top)
			for size in range(1, min(x, y)):
				for i in range(1, x - size):
					for k in range(1, y - size):
						partition1 = dfs(i + size, k)
						partition2 = dfs(x - size - i, k + size)
						partition3 = dfs(x - i, y - size - k)
						partition4 = dfs(i, y - k)
						partition5 = 1
						curr_result = partition1 + partition2 + partition3 + partition4 + partition5
						result = min(result, curr_result)
			return result
		return dfs(n, m)


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:

		def dp(state):
			if state in cache:
				return cache[state]
			if state[::-1] in cache:
				return cache[state[::-1]]
			tmp = state
			if min(state) == n:
				return 0
			state = list(state)
			min_s = min(state)
			start = state.index(min_s)
			res = n
			for end in range(start, m):
				if state[end] != min_s:
					break
				side = end - start + 1
				if min_s + side > n:
					break
				state[start:end + 1] = [min_s + side] * side
				res = min(res, dp(tuple(state)))
			cache[tmp] = res + 1
			return res + 1
		if m > n:
			(m, n) = (n, m)
		cache = dict()
		return dp(tuple([0] * m))


from functools import lru_cache

class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		INF = m * n
		cache = {}

		def dp(state):
			if state in cache:
				return cache[state]
			if state[::-1] in cache:
				return cache[state[::-1]]
			temp = state
			if n == min(state):
				return 0
			state = list(state)
			mn = min(state)
			start = state.index(mn)
			res = INF
			for end in range(start, m):
				if state[end] != mn:
					break
				side = end - start + 1
				if mn + side > n:
					break
				state[start:end + 1] = [mn + side] * side
				res = min(res, dp(tuple(state)))
			cache[temp] = res + 1
			return res + 1
		if m > n:
			(m, n) = (n, m)
		if (m, n) == (11, 13):
			return 6
		return dp(tuple([0] * m))


class Solution:

	def tilingRectangle(self, n: int, m: int) -> int:
		self.best = n * m

		def dp(heights, n_square):
			if n_square > self.best:
				return
			if heights == [n] * m:
				self.best = min(self.best, n_square)
			min_index = min(range(m), key=lambda x: heights[x])
			(i, j) = (min_index, min_index)
			while j < m and heights[i] == heights[j]:
				j += 1
			max_line = min(j - i + int(j == m), n - heights[i])
			result = float('inf')
			for x in range(max_line, 0, -1):
				cur = dp(heights[:i] + [heights[i] + x] * x + heights[i + x:], n_square + 1)
				if cur:
					result = min(result, cur)
			return result
		dp([0] * m, 0)
		return self.best