A board of length M and width N is given. The task is to break this board into M * N squares such that cost of breaking is minimum. The cutting cost for each edge will be given for the board in two arrays X[] and Y[]. In short, you need to choose such a sequence of cutting such that cost is minimized. Return the minimized cost.
Example 1:
Input:
M = 6. N = 4
X[] = {2, 1, 3, 1, 4}
Y[] = {4, 1, 2}
Output: 42
Explanation: 
For above board optimal way to cut into square is:
Total minimum cost in above case is 42. It is 
evaluated using following steps.
Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
Cost 4 Horizontal cut:      Cost = 0 + 4*1 = 4
Cost 4 Vertical cut:        Cost = 4 + 4*2 = 12
Cost 3 Vertical cut:        Cost = 12 + 3*2 = 18
Cost 2 Horizontal cut:      Cost = 18 + 2*3 = 24
Cost 2 Vertical cut:        Cost = 24 + 2*3 = 30
Cost 1 Horizontal cut:      Cost = 30 + 1*4 = 34
Cost 1 Vertical cut:        Cost = 34 + 1*4 = 38
Cost 1 Vertical cut:        Cost = 38 + 1*4 = 42
 
 
Example 2:
Input:
M = 4, N = 4
X[] = {1, 1, 1}
Y[] = {1, 1, 1}
Output: 15
Explanation: 
For above board optimal way to cut into square is:
Total minimum cost in above case is 15.
It is evaluated using following steps.
Initial Value : 
Total_cost = 0 Total_cost = Total_cost + edge_cost * total_pieces
Cost 1 Horizontal cut: Cost = 0 + 1*1 = 1
Cost 1 Horizontal cut: Cost = 1 + 1*1 = 2
Cost 1 Horizontal cut: Cost = 2 + 1*1 = 3
Cost 1 Vertical cut:   Cost = 3 + 1*3 = 6
Cost 1 Vertical cut:   Cost = 6 + 1*3 = 9
Cost 1 Vertical cut: Cost = 9 + 1*3 = 12
Cost 1 Vertical cut:   Cost = 12 + 1*3 = 15
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumCostOfBreaking() which takes a string S and returns an integer as output.
Expected Time Complexity: O(NlogN + MlogM)
Expected Auxiliary Space: O(1)
 
Constraints:
2 <= N, M <= 10^{5}

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(NlogN + MlogM)
Expected Auxiliary Space: O(1)

Starter code:


from typing import List

class Solution:

    def minimumCostOfBreaking(self,X : List[int], Y : List[int],M : int, N : int) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		a = 1
		b = 1
		cost = 0
		while i < M - 1 and j < N - 1:
			if X[i] > Y[j]:
				a = a + 1
				cost = cost + X[i] * b
				i = i + 1
			else:
				b = b + 1
				cost = cost + Y[j] * a
				j = j + 1
		if j == N - 1:
			while i < M - 1:
				cost = cost + X[i] * b
				i = i + 1
		if i == M - 1:
			while j < N - 1:
				cost = cost + Y[j] * a
				j = j + 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		hor_c = 1
		ver_c = 1
		min_cost = 0
		(i, j) = (0, 0)
		m = len(X)
		n = len(Y)
		while i < m and j < n:
			if X[i] > Y[j]:
				min_cost += hor_c * X[i]
				ver_c += 1
				i += 1
			else:
				min_cost += ver_c * Y[j]
				hor_c += 1
				j += 1
		while i < m:
			min_cost += hor_c * X[i]
			i += 1
		while j < n:
			min_cost += ver_c * Y[j]
			j += 1
		return min_cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		ans = 0
		horizontal_count = 1
		vertical_count = 1
		(i, j) = (0, 0)
		m = len(X)
		n = len(Y)
		while i < m and j < n:
			if X[i] > Y[j]:
				ans = ans + X[i] * horizontal_count
				vertical_count += 1
				i += 1
			else:
				ans = ans + Y[j] * vertical_count
				horizontal_count += 1
				j += 1
		while i < m:
			ans += horizontal_count * X[i]
			i += 1
		while j < n:
			ans += vertical_count * Y[j]
			j += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		answer = 0
		horizontal = 1
		vertical = 1
		m = len(X)
		n = len(Y)
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		while i < m and j < n:
			if X[i] > Y[j]:
				answer += horizontal * X[i]
				vertical += 1
				i += 1
			else:
				answer += vertical * Y[j]
				horizontal += 1
				j += 1
		while i < m:
			answer += horizontal * X[i]
			i += 1
		while j < n:
			answer += vertical * Y[j]
			j += 1
		return answer


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		l = []
		for i in X:
			l.append([i, 'x'])
		for i in Y:
			l.append([i, 'y'])
		l.sort(key=lambda x: x[0], reverse=True)
		ans = 0
		x_pieces = 1
		y_pieces = 1
		for (c, edge) in l:
			if edge == 'x':
				ans += c * y_pieces
				x_pieces += 1
			elif edge == 'y':
				ans += c * x_pieces
				y_pieces += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		v = 1
		h = 1
		cost = 0
		while X and Y:
			if X[-1] > Y[-1]:
				x = X.pop()
				cost = cost + x * v
				h = h + 1
			elif X[-1] <= Y[-1]:
				x = Y.pop()
				cost = cost + x * h
				v = v + 1
		while X:
			x = X.pop()
			cost = cost + x * v
			h = h + 1
		while Y:
			x = Y.pop()
			cost = cost + x * h
			v = v + 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		M -= 1
		N -= 1
		total = 0
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		h_piece = 1
		v_piece = 1
		while i < M and j < N:
			if X[i] >= Y[j]:
				total += X[i] * h_piece
				v_piece += 1
				i += 1
			elif X[i] < Y[j]:
				total += Y[j] * v_piece
				h_piece += 1
				j += 1
		while i < M:
			total += X[i] * h_piece
			i += 1
		while j < N:
			total += Y[j] * v_piece
			j += 1
		return total


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		hz = 1
		vt = 1
		X.sort(reverse=True)
		Y.sort(reverse=True)
		ans = 0
		i = 0
		j = 0
		while i < M - 1 and j < N - 1:
			if X[i] >= Y[j]:
				ans += X[i] * hz
				vt += 1
				i += 1
			elif X[i] <= Y[j]:
				ans += Y[j] * vt
				hz += 1
				j += 1
		while i < M - 1:
			ans += X[i] * hz
			i += 1
		while j < N - 1:
			ans += Y[j] * vt
			j += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(ht, vt, ans, i, j) = (1, 1, 0, 0, 0)
		while i < N - 1 or j < M - 1:
			if i == N - 1:
				ans += X[j] * ht
				j += 1
				vt += 1
			elif j == M - 1:
				ans += Y[i] * vt
				i += 1
				ht += 1
			elif Y[i] >= X[j]:
				ans += Y[i] * vt
				i += 1
				ht += 1
			else:
				ans += X[j] * ht
				j += 1
				vt += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		res = 0
		h = 1
		v = 1
		while len(X) > 0 and len(Y) > 0:
			if X[-1] > Y[-1]:
				res += X.pop() * v
				h += 1
			else:
				res += Y.pop() * h
				v += 1
		if len(X) > 0:
			res += sum(X) * v
		if len(Y) > 0:
			res += sum(Y) * h
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		res = 0
		X.sort(reverse=True)
		Y.sort(reverse=True)
		hzntl = 1
		vert = 1
		m = len(X)
		n = len(Y)
		i = 0
		j = 0
		while i < m and j < n:
			if X[i] > Y[j]:
				res += X[i] * vert
				hzntl += 1
				i += 1
			else:
				res += Y[j] * hzntl
				vert += 1
				j += 1
		total = 0
		while i < m:
			total += X[i]
			i += 1
		res += total * vert
		total = 0
		while j < n:
			total += Y[j]
			j += 1
		res += total * hzntl
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, x: List[int], y: List[int], M: int, N: int) -> int:
		x.sort(reverse=True)
		y.sort(reverse=True)
		i = 0
		j = 0
		verc = 1
		horc = 1
		ans = 0
		while i < len(x) and j < len(y):
			if x[i] > y[j]:
				ans += verc * x[i]
				horc += 1
				i += 1
			elif x[i] <= y[j]:
				ans += horc * y[j]
				verc += 1
				j += 1
		while i < len(x):
			ans += verc * x[i]
			i += 1
		while j < len(y):
			ans += horc * y[j]
			j += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		l = 1
		r = 1
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		res = 0
		while i < M - 1 or j < N - 1:
			if i < M - 1 and (j >= N - 1 or X[i] > Y[j]):
				res += X[i] * l
				r += 1
				i += 1
			else:
				res += Y[j] * r
				l += 1
				j += 1
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, hrz: List[int], vert: List[int], M: int, N: int) -> int:
		hrz.sort(reverse=True)
		vert.sort(reverse=True)
		m = len(X)
		n = len(Y)
		ans = 0
		v_count = 1
		h_count = 1
		i = 0
		j = 0
		while i < m and j < n:
			if hrz[i] > vert[j]:
				ans += hrz[i] * h_count
				v_count += 1
				i += 1
			else:
				ans += vert[j] * v_count
				h_count += 1
				j += 1
		while i < m:
			ans += hrz[i] * h_count
			v_count += 1
			i += 1
		while j < n:
			ans += vert[j] * v_count
			h_count += 1
			j += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, x: List[int], y: List[int], m: int, n: int) -> int:
		x.sort()
		y.sort()
		m -= 1
		n -= 1
		i = m - 1
		j = n - 1
		cost = 0
		rows = cols = 1
		while i > -1 and j > -1:
			if x[i] > y[j]:
				cost += x[i] * rows
				i -= 1
				cols += 1
			else:
				cost += y[j] * cols
				j -= 1
				rows += 1
		while i > -1:
			cost += x[i] * rows
			i -= 1
		while j > -1:
			cost += y[j] * cols
			j -= 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		horizontal_cuts = 1
		vertical_cuts = 1
		X.sort()
		Y.sort()
		m = len(X) - 1
		n = len(Y) - 1
		cost = 0
		while m >= 0 and n >= 0:
			if X[m] >= Y[n]:
				cost += vertical_cuts * X[m]
				horizontal_cuts += 1
				m -= 1
			else:
				cost += horizontal_cuts * Y[n]
				vertical_cuts += 1
				n -= 1
		while m >= 0:
			cost += vertical_cuts * X[m]
			horizontal_cuts += 1
			m -= 1
		while n >= 0:
			cost += horizontal_cuts * Y[n]
			vertical_cuts += 1
			n -= 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		V = 1
		H = 1
		ans = 0
		while i < M - 1 and j < N - 1:
			if X[i] > Y[j]:
				ans += X[i] * H
				i += 1
				V += 1
			else:
				ans += Y[j] * V
				j += 1
				H += 1
		while i < M - 1:
			ans += X[i] * H
			i += 1
			V += 1
		while j < N - 1:
			ans += Y[j] * V
			j += 1
			H += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		hz = 1
		vz = 1
		i = 0
		j = 0
		result = 0
		M = M - 1
		N = N - 1
		while i < M and j < N:
			if X[i] >= Y[j]:
				result += X[i] * vz
				hz += 1
				i += 1
			else:
				result += Y[j] * hz
				vz += 1
				j += 1
		total = 0
		while i < M:
			total += X[i]
			i += 1
		result += total * vz
		total = 0
		while j < N:
			total += Y[j]
			j += 1
		result += total * hz
		return result


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(i, j) = (0, 0)
		(M, N) = (M - 1, N - 1)
		(h, v) = (1, 1)
		res = 0
		while i < M and j < N:
			if X[i] > Y[j]:
				res = res + X[i] * h
				v += 1
				i += 1
			else:
				res = res + Y[j] * v
				h += 1
				j += 1
		while i < M:
			res = res + X[i] * h
			v += 1
			i += 1
		while j < N:
			res = res + Y[j] * v
			h += 1
			j += 1
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		(i, j) = (M - 2, N - 2)
		(h, v) = (1, 1)
		total = 0
		while i >= 0 and j >= 0:
			if X[i] > Y[j]:
				total += X[i] * v
				h += 1
				i -= 1
			else:
				total += Y[j] * h
				v += 1
				j -= 1
		if i == -1:
			total += sum(Y[:j + 1]) * h
		else:
			total += sum(X[:i + 1]) * v
		return total


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		xPointer = 0
		yPointer = 0
		verticalPieces = 1
		horizontalPieces = 1
		total = 0
		while xPointer < M - 1 and yPointer < N - 1:
			if X[xPointer] > Y[yPointer]:
				total += X[xPointer] * horizontalPieces
				xPointer += 1
				verticalPieces += 1
			else:
				total += Y[yPointer] * verticalPieces
				yPointer += 1
				horizontalPieces += 1
		while xPointer < M - 1:
			total += X[xPointer] * horizontalPieces
			xPointer += 1
			verticalPieces += 1
		while yPointer < N - 1:
			total += Y[yPointer] * verticalPieces
			yPointer += 1
			horizontalPieces += 1
		return total


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		cost = 0
		arr = []
		for i in X:
			arr.append([i, 'h'])
		for i in Y:
			arr.append([i, 'v'])
		arr.sort(key=lambda a: a[0], reverse=True)
		(h, v, k) = (1, 1, 0)
		while k < len(arr):
			if arr[k][1] == 'h':
				cost += v * arr[k][0]
				h += 1
			else:
				cost += h * arr[k][0]
				v += 1
			k += 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		i = 0
		j = 0
		count = 0
		while i < M - 1 and j < N - 1:
			if X[i] > Y[j]:
				count += X[i] * (j + 1)
				i += 1
			else:
				count += Y[j] * (i + 1)
				j += 1
		if j == N - 1:
			for x in range(i, M - 1):
				count += X[x] * N
		else:
			for x in range(j, N - 1):
				count += Y[x] * M
		return count


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		summa = 0
		x = 1
		y = 1
		while True:
			if X[0] > Y[0]:
				summa += X.pop(0) * y
				x += 1
			else:
				summa += Y.pop(0) * x
				y += 1
			if not len(X):
				while len(Y):
					summa += Y.pop(0) * x
				break
			if not len(Y):
				while len(X):
					summa += X.pop(0) * y
				break
		return summa


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(i, j) = (0, 0)
		min_total_cost = 0
		(hori, verti) = (1, 1)
		while i < M - 1 and j < N - 1:
			if X[i] >= Y[j]:
				min_total_cost += X[i] * hori
				i += 1
				verti += 1
			else:
				min_total_cost += Y[j] * verti
				j += 1
				hori += 1
		rmng_x = 0
		while i < M - 1:
			rmng_x += X[i]
			i += 1
		min_total_cost += rmng_x * hori
		rmng_y = 0
		while j < N - 1:
			rmng_y += Y[j]
			j += 1
		min_total_cost += rmng_y * verti
		return min_total_cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(i, j) = (0, 0)
		(hori, verti) = (1, 1)
		min_cost = 0
		while i < M - 1 and j < N - 1:
			if X[i] >= Y[j]:
				min_cost += X[i] * hori
				i += 1
				verti += 1
			else:
				min_cost += Y[j] * verti
				j += 1
				hori += 1
		rmng_X = 0
		while i < M - 1:
			rmng_X += X[i]
			i += 1
		min_cost += rmng_X * hori
		rmng_Y = 0
		while j < N - 1:
			rmng_Y += Y[j]
			j += 1
		min_cost += rmng_Y * verti
		return min_cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		min_cost = 0
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(i, j) = (0, 0)
		(horizontal, vertical) = (1, 1)
		while i < M - 1 and j < N - 1:
			if X[i] >= Y[j]:
				min_cost += X[i] * vertical
				i += 1
				horizontal += 1
			else:
				min_cost += Y[j] * horizontal
				j += 1
				vertical += 1
		total = 0
		while i < M - 1:
			total += X[i]
			i += 1
		min_cost += total * vertical
		total = 0
		while j < N - 1:
			total += Y[j]
			j += 1
		min_cost += total * horizontal
		return min_cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, x: List[int], y: List[int], m: int, n: int) -> int:
		res = 0
		x.sort(reverse=True)
		y.sort(reverse=True)
		hzntl = 1
		vert = 1
		i = 0
		j = 0
		while i < m - 1 and j < n - 1:
			if x[i] > y[j]:
				res += x[i] * hzntl
				vert += 1
				i += 1
			else:
				res += y[j] * vert
				hzntl += 1
				j += 1
		while i < m - 1:
			res += x[i] * hzntl
			vert += 1
			i += 1
		while j < n - 1:
			res += y[j] * vert
			hzntl += 1
			j += 1
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, vertical: List[int], horizontal: List[int], M: int, N: int) -> int:
		vertical.sort(reverse=True)
		horizontal.sort(reverse=True)
		horiCount = 1
		vertiCount = 1
		i = 0
		j = 0
		cost = 0
		while i < len(vertical) and j < len(horizontal):
			if vertical[i] > horizontal[j]:
				cost += vertiCount * vertical[i]
				horiCount += 1
				i += 1
			else:
				cost += horiCount * horizontal[j]
				vertiCount += 1
				j += 1
		while i < len(vertical):
			cost += vertiCount * vertical[i]
			i += 1
		while j < len(horizontal):
			cost += horiCount * horizontal[j]
			j += 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		costV = X
		costH = Y
		Vpieces = 1
		Hpieces = 1
		costV.sort(reverse=True)
		costH.sort(reverse=True)
		i = 0
		j = 0
		price = 0
		while i < len(costV) and j < len(costH):
			if costV[i] >= costH[j]:
				price += costV[i] * Vpieces
				Hpieces += 1
				i += 1
			else:
				price += costH[j] * Hpieces
				Vpieces += 1
				j += 1
		while i < len(costV):
			price += costV[i] * Vpieces
			i += 1
		while j < len(costH):
			price += costH[j] * Hpieces
			j += 1
		return price


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		m = M - 1
		n = N - 1
		x = sorted(X, reverse=True)
		y = sorted(Y, reverse=True)
		hc = 1
		vc = 1
		ans = 0
		i = 0
		j = 0
		while i < m and j < n:
			if x[i] > y[j]:
				ans += x[i] * vc
				hc += 1
				i += 1
			else:
				ans += y[j] * hc
				vc += 1
				j += 1
		while i < m:
			ans += x[i] * vc
			i += 1
		while j < n:
			ans += y[j] * hc
			j += 1
		return ans


from collections import deque
from collections import defaultdict
from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		x = deque(sorted(X, reverse=True))
		y = deque(sorted(Y, reverse=True))
		cut_x = 1
		cut_y = 1
		Sum = 0
		flag = 1
		while len(x) != 0 or len(y) != 0:
			if len(x) != 0 and (len(y) == 0 or x[0] >= y[0]):
				temp = x.popleft()
				flag = 1
			else:
				temp = y.popleft()
				flag = 0
			if flag:
				Sum += cut_x * temp
				cut_y += 1
			else:
				Sum += cut_y * temp
				cut_x += 1
		return Sum


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		M -= 1
		N -= 1
		X.sort(reverse=True)
		Y.sort(reverse=True)
		horizontal_count = 1
		vertical_count = 1
		total_cost = 0
		i = 0
		j = 0
		while i < M and j < N:
			if X[i] > Y[j]:
				total_cost += X[i] * vertical_count
				horizontal_count += 1
				i += 1
			else:
				total_cost += Y[j] * horizontal_count
				vertical_count += 1
				j += 1
		while i < M:
			total_cost += X[i] * vertical_count
			i += 1
		while j < N:
			total_cost += Y[j] * horizontal_count
			j += 1
		return total_cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		c = 1
		r = 1
		i = 0
		j = 0
		cost = 0
		while i < len(X) and j < len(Y):
			if X[i] >= Y[j]:
				cost += X[i] * r
				c += 1
				i += 1
			else:
				cost += Y[j] * c
				r += 1
				j += 1
		while i < len(X):
			cost += X[i] * r
			i += 1
		while j < len(Y):
			cost += Y[j] * c
			j += 1
		return cost


from typing import List

class Solution:

	def maxi(X, Y):
		if len(X) == 0:
			return 'y'
		elif len(Y) == 0:
			return 'x'
		elif max(X) > max(Y):
			return 'x'
		else:
			return 'y'

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		h = 1
		v = 1
		c = 0
		while h * v != M * N:
			l = Solution.maxi(X, Y)
			if l == 'x':
				h += 1
				c += v * max(X)
				X.pop(-1)
			elif l == 'y':
				v += 1
				c += h * max(Y)
				Y.pop(-1)
		return c


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		cost = 0
		(H_piece, V_piece) = (1, 1)
		(idx_x, idx_y) = (len(X) - 1, len(Y) - 1)
		while idx_x >= 0 and idx_y >= 0:
			if X[idx_x] > Y[idx_y]:
				cost += H_piece * X[idx_x]
				idx_x -= 1
				V_piece += 1
			else:
				cost += V_piece * Y[idx_y]
				idx_y -= 1
				H_piece += 1
		while idx_x >= 0:
			cost += H_piece * X[idx_x]
			idx_x -= 1
			V_piece += 1
		while idx_y >= 0:
			cost += V_piece * Y[idx_y]
			idx_y -= 1
			H_piece += 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		L = []
		for i in X:
			L.append([i, 'x'])
		for i in Y:
			L.append([i, 'y'])
		L.sort(key=lambda x: x[0], reverse=True)
		x_piece = 1
		y_piece = 1
		ans = 0
		for (c, edge) in L:
			if edge == 'x':
				ans += c * y_piece
				x_piece += 1
			elif edge == 'y':
				ans += c * x_piece
				y_piece += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		xCut = 1
		yCut = 1
		currPrice = 0
		i = len(X) - 1
		j = len(Y) - 1
		while i >= 0 and j >= 0:
			if X[i] > Y[j]:
				currPrice += X[i] * xCut
				yCut += 1
				i -= 1
			elif X[i] < Y[j]:
				currPrice += Y[j] * yCut
				xCut += 1
				j -= 1
			elif X[i] == Y[j]:
				if xCut > yCut:
					currPrice += X[i] * xCut
					yCut += 1
					i -= 1
				else:
					currPrice += Y[j] * yCut
					xCut += 1
					j -= 1
		while i >= 0:
			currPrice += X[i] * xCut
			yCut += 1
			i -= 1
		while j >= 0:
			currPrice += Y[j] * yCut
			xCut += 1
			j -= 1
		return currPrice


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		h = 1
		v = 1
		ans = 0
		i = 0
		j = 0
		while i < m - 1 and j < n - 1:
			if X[i] > Y[j]:
				ans += v * X[i]
				h = h + 1
				i = i + 1
			else:
				ans += h * Y[j]
				v = v + 1
				j = j + 1
		while i < m - 1:
			ans += v * X[i]
			i = i + 1
		while j < n - 1:
			ans += h * Y[j]
			j = j + 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		(vcuts, hcuts) = (1, 1)
		arr = sorted([(v, 'v') for v in X] + [(v, 'h') for v in Y], key=lambda x: x[0], reverse=True)
		ans = 0
		for (a, o) in arr:
			if o == 'v':
				ans += hcuts * a
				vcuts += 1
			elif o == 'h':
				ans += vcuts * a
				hcuts += 1
		return ans


from heapq import heapify, heappop as hpop
from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		hpiece = 1
		vpiece = 1
		heap = []
		for i in range(M - 1):
			heap.append((-X[i], 1))
		for i in range(N - 1):
			heap.append((-Y[i], 0))
		heapify(heap)
		res = 0
		while heap:
			(cst, dirn) = hpop(heap)
			cst = -cst
			if dirn:
				res += cst * vpiece
				hpiece += 1
			else:
				res += cst * hpiece
				vpiece += 1
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		xc = yc = c = 0
		while xc < M - 1 and yc < N - 1:
			if X[-1] > Y[-1]:
				c += (yc + 1) * X.pop()
				xc += 1
			else:
				c += (xc + 1) * Y.pop()
				yc += 1
		while xc < M - 1:
			c += (yc + 1) * X.pop()
			xc += 1
		while yc < N - 1:
			c += (xc + 1) * Y.pop()
			yc += 1
		return c


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		hz = 1
		vz = 1
		i = 0
		j = 0
		totalcost = 0
		while i < m - 1 and j < n - 1:
			if X[i] >= Y[j]:
				totalcost = totalcost + hz * X[i]
				i += 1
				vz += 1
			else:
				totalcost = totalcost + vz * Y[j]
				j += 1
				hz += 1
		while i < m - 1:
			totalcost = totalcost + hz * X[i]
			i += 1
			vz += 1
		while j < n - 1:
			totalcost = totalcost + vz * Y[j]
			j += 1
			hz += 1
		return totalcost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		if len(X) > len(Y):
			(X, Y) = (Y, X)
		X = sorted(X, reverse=True)
		Y = sorted(Y, reverse=True)
		(m, n) = (len(X), len(Y))
		(i, j) = (0, 0)
		cost = 0
		(hori, verti) = (1, 1)
		while i < m and j < n:
			if X[i] < Y[j]:
				hori += 1
				cost += Y[j] * verti
				j += 1
			elif Y[j] <= X[i]:
				verti += 1
				cost += X[i] * hori
				i += 1
		if i == m:
			while j < n:
				cost = cost + Y[j] * verti
				j += 1
		if j == n:
			while i < m:
				cost = cost + X[i] * hori
				i += 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		(ver, hor) = (1, 1)
		(i, j) = (len(X) - 1, len(Y) - 1)
		cost = 0
		while i >= 0 and j >= 0:
			if X[i] > Y[j]:
				cost += X[i] * ver
				hor += 1
				i -= 1
			else:
				cost += Y[j] * hor
				ver += 1
				j -= 1
		while i >= 0:
			cost += X[i] * ver
			i -= 1
		while j >= 0:
			cost += Y[j] * hor
			j -= 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, cols: List[int], rows: List[int], M: int, N: int) -> int:
		vcut = hcut = 1
		rows.sort(reverse=True)
		cols.sort(reverse=True)
		i = j = 0
		cost = 0
		while i < len(rows) and j < len(cols):
			if rows[i] > cols[j]:
				cost = cost + rows[i] * vcut
				hcut += 1
				i = i + 1
			else:
				cost = cost + cols[j] * hcut
				vcut += 1
				j = j + 1
		while i < len(rows):
			cost = cost + rows[i] * vcut
			hcut += 1
			i = i + 1
		while j < len(cols):
			cost = cost + cols[j] * hcut
			vcut += 1
			j = j + 1
		return cost


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		res = 0
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(horizontal, vertical) = (1, 1)
		(i, j) = (0, 0)
		while i < m - 1 and j < n - 1:
			if X[i] > Y[j]:
				res += X[i] * vertical
				horizontal += 1
				i += 1
			else:
				res += Y[j] * horizontal
				vertical += 1
				j += 1
		total = 0
		while i < m - 1:
			total += X[i]
			i += 1
		res += total * vertical
		total = 0
		while j < n - 1:
			total += Y[j]
			j += 1
		res += total * horizontal
		return res


from typing import List

class Solution:

	def minimumCostOfBreaking(self, x: List[int], y: List[int], M: int, N: int) -> int:
		x.sort()
		y.sort()
		v_p = 1
		h_p = 1
		ans = 0
		while x or y:
			if not y:
				k = x.pop()
				h_p += 1
				ans += k * v_p
			elif not x:
				k = y.pop()
				v_p += 1
				ans += k * h_p
			elif y[-1] >= x[-1]:
				k = y.pop()
				v_p += 1
				ans += k * h_p
			else:
				k = x.pop()
				h_p += 1
				ans += k * v_p
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort()
		Y.sort()
		i = 1
		j = 1
		t = 0
		while i <= len(X) and j <= len(Y):
			if X[-i] >= Y[-j]:
				t += X[-i] * j
				i += 1
			elif X[-i] < Y[-j]:
				t += Y[-j] * i
				j += 1
		if i < len(X) + 1:
			while i < len(X) + 1:
				t += X[-i] * (len(Y) + 1)
				i += 1
		if j < len(Y) + 1:
			while j < len(Y) + 1:
				t += Y[-j] * (len(X) + 1)
				j += 1
		return t


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		tc = 0
		hc = 1
		vc = 1
		(i, j) = (0, 0)
		while i < M - 1 and j < N - 1:
			if X[i] > Y[j]:
				tc += X[i] * hc
				vc += 1
				i += 1
			else:
				tc += Y[j] * vc
				hc += 1
				j += 1
		while i < M - 1:
			tc += X[i] * hc
			vc += 1
			i += 1
		while j < N - 1:
			tc += Y[j] * vc
			hc += 1
			j += 1
		return tc


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], M: int, N: int) -> int:
		(v, h) = (1, 1)
		ans = 0
		l = sorted([(i, 1) for i in X] + [(j, 0) for j in Y], key=lambda x: -x[0])
		for (i, d) in l:
			if d == 0:
				ans += h * i
				v += 1
			if d == 1:
				ans += v * i
				h += 1
		return ans


from typing import List

class Solution:

	def minimumCostOfBreaking(self, X: List[int], Y: List[int], m: int, n: int) -> int:
		X.sort(reverse=True)
		Y.sort(reverse=True)
		(x, y) = (1, 1)
		cost = 0
		(i, j) = (0, 0)
		while i < len(X) and j < len(Y):
			if X[i] > Y[j]:
				cost += x * X[i]
				y += 1
				i += 1
			else:
				cost += y * Y[j]
				x += 1
				j += 1
		while i < len(X):
			cost += x * X[i]
			i += 1
		while j < len(Y):
			cost += y * Y[j]
			j += 1
		return cost