Given two strings X and Y, and two values costX and costY, the task is to find the minimum cost required to make the given two strings identical. You can delete characters from both the strings. The cost of deleting a character from string X is costX and from Y is costY. The cost of removing all characters from a string is the same.
Example 1:
Input: X = "abcd", Y = "acdb", costX = 10 
       costY = 20.
Output: 30
Explanation: For Making both strings 
identical we have to delete character 
'b' from both the string, hence cost 
will be = 10 + 20 = 30.
Example 2:
Input : X = "ef", Y = "gh", costX = 10
        costY = 20.
Output: 60
Explanation: For making both strings 
identical, we have to delete 2-2 
characters from both the strings, hence 
cost will be = 10 + 10 + 20 + 20 = 60.
Your Task:
You don't need to read or print anything. Your task is to complete the function findMinCost() which takes both strings and the costs as input parameters and returns the minimum cost.
Expected Time Complexity: O(|X|*|Y|)
Expected Space Complexity: O(|X|*|Y|)
Constraints:
1 ≤ |X|, |Y| ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def findMinCost(self, X, Y, costX, costY):
		# code here

Solutions:
class Solution:

	def findMinCost(self, X, Y, costX, costY):
		lcs = self.longest_common_substring(X, Y)
		(n, m) = (len(X), len(Y))
		ans = (n - lcs) * costX + (m - lcs) * costY
		return ans

	def longest_common_substring(self, a, b):
		n = len(a)
		m = len(b)
		dp = [[-1] * (m + 1) for i in range(n + 1)]

		def lcs(a, b, i, j):
			if i == len(a) or j == len(b):
				dp[i][j] = 0
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if a[i] == b[j]:
				dp[i][j] = 1 + lcs(a, b, i + 1, j + 1)
			else:
				dp[i][j] = max(lcs(a, b, i, j + 1), lcs(a, b, i + 1, j))
			return dp[i][j]
		return lcs(a, b, 0, 0)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		(m, n) = (len(X), len(Y))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for row in range(1, m + 1):
			dp[row][0] = dp[row - 1][0] + costX
		for col in range(1, n + 1):
			dp[0][col] = dp[0][col - 1] + costY
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i - 1][j] + costX, dp[i][j - 1] + costY)
		return dp[-1][-1]


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = [[0] * (len(Y) + 1) for i in range(len(X) + 1)]
		for i in range(len(X) + 1):
			for j in range(len(Y) + 1):
				if i == 0:
					dp[i][j] = j * costY
				elif j == 0:
					dp[i][j] = i * costX
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i - 1][j] + costX, dp[i][j - 1] + costY)
		return dp[len(X)][len(Y)]


class Solution:

	def findMinCost(self, strg1, strg2, costX, costY):
		m = len(strg1)
		n = len(strg2)
		tab = []
		for i in range(m + 1):
			ls = [-1] * (n + 1)
			tab.append(ls)
		for i in range(m + 1):
			tab[i][0] = 0
		for i in range(n + 1):
			tab[0][i] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if strg1[i - 1] == strg2[j - 1]:
					tab[i][j] = 1 + tab[i - 1][j - 1]
				else:
					tab[i][j] = max(tab[i - 1][j], tab[i][j - 1])
		lcs = tab[m][n]
		total = 0
		total += (m - lcs) * costX
		total += (n - lcs) * costY
		return total


class Solution:

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

	def findMinCost(self, X, Y, costX, costY):
		if (X, Y) in self.memo:
			return self.memo[X, Y]
		if len(X) == 0 and len(Y) == 0:
			self.memo[X, Y] = 0
		elif len(X) == 0:
			self.memo[X, Y] = costY + self.findMinCost(X, Y[1:], costX, costY)
		elif len(Y) == 0:
			self.memo[X, Y] = costX + self.findMinCost(X[1:], Y, costX, costY)
		elif X[0] == Y[0]:
			self.memo[X, Y] = self.findMinCost(X[1:], Y[1:], costX, costY)
		else:
			self.memo[X, Y] = min(self.findMinCost(X[1:], Y, costX, costY) + costX, self.findMinCost(X, Y[1:], costX, costY) + costY)
		return self.memo[X, Y]


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		add = costX + costY
		t = [[0 for x in range(m + 1)] for x in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 or j == 0:
					t[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		k = t[n][m]
		a = (n - k) * costX + (m - k) * costY
		return a


class Solution:

	def findMinCost(self, s1, s2, costx, costy):
		x = len(s1)
		y = len(s2)
		l = [[0 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					l[i][j] = l[i - 1][j - 1] + 1
				else:
					l[i][j] = max(l[i - 1][j], l[i][j - 1])
		return (x - l[x][y]) * costx + (y - l[x][y]) * costy


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		dp = [[0 for i in range(len(Y) + 1)] for i in range(len(X) + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		z = costX * abs(m - dp[-1][-1]) + costY * abs(n - dp[-1][-1])
		return z


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		x = len(X)
		y = len(Y)
		m = []
		for i in range(x + 1):
			l = []
			for j in range(y + 1):
				l.append(0)
			m.append(l)
		for i in range(1, x + 1):
			for j in range(1, y + 1):
				if X.__getitem__(i - 1) == Y.__getitem__(j - 1):
					m[i][j] = m[i - 1][j - 1] + 1
				else:
					m[i][j] = max(m[i - 1][j], m[i][j - 1])
		g = m[i][j]
		return (len(X) - g) * costX + (len(Y) - g) * costY
		x = len(X)
		y = len(Y)
		m2 = []
		for i in range(y + 1):
			l = []
			for j in range(x + 1):
				l.append(0)
			m2.append(l)


class Solution:

	def findMinCost(self, a, b, costX, costY):
		la = len(a)
		lb = len(b)
		dp = [[0 for i in range(lb + 1)] for j in range(la + 1)]
		for x in range(1, la + 1):
			for y in range(1, lb + 1):
				dp[x][y] = -1

		def lcs(a, b, dp, la, lb):
			if la == 0 or lb == 0:
				return 0
			if dp[la][lb] != -1:
				return dp[la][lb]
			if a[la - 1] == b[lb - 1]:
				dp[la][lb] = 1 + lcs(a, b, dp, la - 1, lb - 1)
				return dp[la][lb]
			else:
				dp[la][lb] = max(lcs(a, b, dp, la - 1, lb), lcs(a, b, dp, la, lb - 1))
				return dp[la][lb]
		result = lcs(a, b, dp, la, lb)
		s1 = la - result
		s2 = lb - result
		final = s1 * costX + s2 * costY
		return final


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]

		def recur(n, m):
			if m == 0:
				return costX * n
			if n == 0:
				return costY * m
			if dp[n][m] != -1:
				return dp[n][m]
			if X[n - 1] == Y[m - 1]:
				res = recur(n - 1, m - 1)
			else:
				res = min(recur(n - 1, m) + costX, recur(n, m - 1) + costY)
			dp[n][m] = res
			return dp[n][m]
		return recur(n, m)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):

		def longestCommonSubsequence(X, Y) -> int:
			dp = [[0 for _ in range(len(Y) + 1)] for _ in range(len(X) + 1)]
			for i in range(len(X)):
				dp[i][0] = 0
			for j in range(len(Y)):
				dp[0][j] = 0
			for i in range(1, len(X) + 1):
				for j in range(1, len(Y) + 1):
					if X[i - 1] == Y[j - 1]:
						dp[i][j] = 1 + dp[i - 1][j - 1]
					else:
						dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
			return dp[-1][-1]
		val = longestCommonSubsequence(X, Y)
		final = costX * (len(X) - val) + costY * (len(Y) - val)
		return final
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		lcs = self.lcs(X, Y, len(X), len(Y))
		x_cost = (len(X) - lcs) * costX
		y_cost = (len(Y) - lcs) * costY
		return x_cost + y_cost

	def lcs(self, a, b, x, y):
		dp = [[0 for j in range(x + 1)] for i in range(y + 1)]
		for i in range(1, y + 1):
			for j in range(1, x + 1):
				if a[j - 1] == b[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return dp[y][x]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		l = [[0] * (n + 1) for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					l[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					l[i][j] = 1 + l[i - 1][j - 1]
				else:
					l[i][j] = max(l[i][j - 1], l[i - 1][j])
		l1 = max(l)
		m = max(l1)
		if len(X) == len(Y):
			dif = len(X) - m
			res = dif * costX + dif * costY
		else:
			dif1 = len(X) - m
			dif2 = len(Y) - m
			res = dif1 * costX + dif2 * costY
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		ans = self.Count(n - 1, m - 1, X, Y, dp)
		res = (n - ans) * costX + (m - ans) * costY
		return res

	def Count(self, ind1, ind2, s1, s2, dp):
		if ind1 < 0 or ind2 < 0:
			return 0
		if dp[ind1][ind2] != -1:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			dp[ind1][ind2] = 1 + self.Count(ind1 - 1, ind2 - 1, s1, s2, dp)
			return dp[ind1][ind2]
		else:
			dp[ind1][ind2] = 0 + max(self.Count(ind1 - 1, ind2, s1, s2, dp), self.Count(ind1, ind2 - 1, s1, s2, dp))
			return dp[ind1][ind2]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)

		def check(i, j):
			if i < 0:
				return 0
			if j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if X[i] == Y[j]:
				dp[i][j] = 1 + check(i - 1, j - 1)
				return dp[i][j]
			elif X[i] != Y[j]:
				dp[i][j] = max(check(i, j - 1), check(i - 1, j))
				return dp[i][j]
		dp = [[-1 for i in range(n)] for i in range(m)]
		m1 = check(m - 1, n - 1)
		ans = (m - m1) * costX + (n - m1) * costY
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		t = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				t[i][j] = 1 + t[i - 1][j - 1] if X[i - 1] == Y[j - 1] else max(t[i - 1][j], t[i][j - 1])
		a = costX * (m - t[m][n])
		b = costY * (n - t[m][n])
		return a + b
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


class Solution:

	def findMinCost(self, x, y, costX, costY):
		dp = [[-1 for i in range(len(y) + 1)] for j in range(len(x) + 1)]
		for i in range(len(dp) - 1, -1, -1):
			for j in range(len(dp[i]) - 1, -1, -1):
				if i == len(dp) - 1 or j == len(dp[i]) - 1:
					dp[i][j] = 0
				elif x[i] == y[j]:
					dp[i][j] = dp[i + 1][j + 1] + 1
				else:
					dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
		r = len(x) - dp[0][0]
		s = len(y) - dp[0][0]
		return r * costX + s * costY
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(X, Y, costX, costY) = input().split()
		costX = int(costX)
		costY = int(costY)
		ob = Solution()
		ans = ob.findMinCost(X, Y, costX, costY)
		print(ans)


def lcs(X, Y, m, n, dp):
	if m == 0 or n == 0:
		return 0
	if dp[m][n] != -1:
		return dp[m][n]
	if X[m - 1] == Y[n - 1]:
		dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp)
		return dp[m][n]
	dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp))
	return dp[m][n]

class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = [[-1 for i in range(len(Y) + 1)] for j in range(len(X) + 1)]
		ans = lcs(X, Y, len(X), len(Y), dp)
		k = 0
		k += (len(X) - ans) * costX + (len(Y) - ans) * costY
		return k


class Solution:

	def f(self, x, y, i, j, dp):
		if i < 0 or j < 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		if x[i] == y[j]:
			dp[i][j] = 1 + self.f(x, y, i - 1, j - 1, dp)
			return dp[i][j]
		dp[i][j] = max(self.f(x, y, i - 1, j, dp), self.f(x, y, i, j - 1, dp))
		return dp[i][j]

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		dp = [[-1 for i in range(n)] for j in range(m)]
		c = self.f(X, Y, m - 1, n - 1, dp)
		f = m - c
		s = n - c
		res = f * costX + s * costY
		return res


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		data = [[0 for i in range(len(X) + 1)] for i in range(len(Y) + 1)]
		for i in range(len(Y) + 1):
			for j in range(len(X) + 1):
				if i == 0 or j == 0:
					continue
				elif Y[i - 1] == X[j - 1]:
					data[i][j] = data[i - 1][j - 1] + 1
				else:
					data[i][j] = max(data[i - 1][j], data[i][j - 1])
		return costX * (len(X) - data[len(Y)][len(X)]) + costY * (len(Y) - data[len(Y)][len(X)])


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		arr = [['' for i in range(len(Y) + 1)] for j in range(len(X) + 1)]
		for i in range(1, len(X) + 1):
			for j in range(1, len(Y) + 1):
				if X[i - 1] == Y[j - 1]:
					arr[i][j] += arr[i - 1][j - 1]
					arr[i][j] += X[i - 1]
				elif len(arr[i - 1][j]) >= len(arr[i][j - 1]):
					arr[i][j] += arr[i - 1][j]
				else:
					arr[i][j] += arr[i][j - 1]
		ans = 0
		j = 0
		for i in range(len(X)):
			if j < len(arr[-1][-1]) and X[i] == arr[-1][-1][j]:
				j += 1
			else:
				ans += costX
		j = 0
		for i in range(len(Y)):
			if j < len(arr[-1][-1]) and Y[i] == arr[-1][-1][j]:
				j += 1
			else:
				ans += costY
		return ans


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = [[0 for i in range(len(Y) + 1)] for j in range(len(X) + 1)]
		for i in range(1, len(X) + 1):
			for j in range(1, len(Y) + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		ans = dp[len(X)][len(Y)]
		return (len(X) - ans) * costX + (len(Y) - ans) * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = [[0 for c in range(len(Y) + 1)] for r in range(len(X) + 1)]
		for r in range(len(dp) - 1, -1, -1):
			for c in range(len(dp[0]) - 1, -1, -1):
				if r == len(dp) - 1 and c == len(dp[0]) - 1:
					dp[r][c] = 0
				elif r == len(dp) - 1:
					dp[r][c] = 0
				elif c == len(dp[0]) - 1:
					dp[r][c] = 0
				elif X[r] == Y[c]:
					dp[r][c] = 1 + dp[r + 1][c + 1]
				else:
					dp[r][c] = max(dp[r][c + 1], dp[r + 1][c])
		lcs = dp[0][0]
		X_del_count = len(X) - lcs
		Y_del_count = len(Y) - lcs
		X_cost = costX * X_del_count
		Y_cost = costY * Y_del_count
		total_cost = X_cost + Y_cost
		return total_cost


class Solution:

	def findMinCost(self, X, Y, costX, costY):

		def mincost(i, j, dp):
			if i == m:
				return (n - j) * costY
			if j == n:
				return (m - i) * costX
			if dp[i][j] != -1:
				return dp[i][j]
			if x[i] == y[j]:
				dp[i][j] = mincost(i + 1, j + 1, dp)
			else:
				dp[i][j] = min(costX + mincost(i + 1, j, dp), costY + mincost(i, j + 1, dp))
			return dp[i][j]
		(x, y) = (X, Y)
		(m, n) = (len(X), len(Y))
		dp = [[-1] * n for _ in range(m)]
		return mincost(0, 0, dp)


class Solution:

	def findMinCost(self, text1, text2, costX, costY):
		(m, n) = (len(text1), len(text2))
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if text1[i - 1] == text2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return costX * (m - dp[i][j]) + costY * (n - dp[i][j])


class Solution:

	def recur(self, ind1, ind2, s1, s2, x, y):
		global dp
		if ind1 == -1 and ind2 == -1:
			return 0
		if ind1 == -1:
			return (ind2 + 1) * y
		if ind2 == -1:
			return (ind1 + 1) * x
		if dp[ind1][ind2]:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			dp[ind1][ind2] = self.recur(ind1 - 1, ind2 - 1, s1, s2, x, y)
			return dp[ind1][ind2]
		rl = x + self.recur(ind1 - 1, ind2, s1, s2, x, y)
		rr = y + self.recur(ind1, ind2 - 1, s1, s2, x, y)
		dp[ind1][ind2] = min(rl, rr)
		return dp[ind1][ind2]

	def findMinCost(self, s1, s2, x, y):
		dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
		for i in range(len(s1) + 1):
			for j in range(len(s2) + 1):
				if i == 0 and j == 0:
					continue
				elif i == 0:
					dp[i][j] = j * y
				elif j == 0:
					dp[i][j] = i * x
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(x + dp[i - 1][j], y + dp[i][j - 1])
		return dp[-1][-1]


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = {}

		def helper(indx1, indx2):
			if (indx1, indx2) in dp:
				return dp[indx1, indx2]
			if indx1 == len(X) and indx2 == len(Y):
				return 0
			if indx1 == len(X):
				return (len(Y) - indx2) * costY
			if indx2 == len(Y):
				return (len(X) - indx1) * costX
			if X[indx1] == Y[indx2]:
				return helper(indx1 + 1, indx2 + 1)
			else:
				dp[indx1, indx2] = min(costX + helper(indx1 + 1, indx2), costY + helper(indx1, indx2 + 1))
			return dp[indx1, indx2]
		return helper(0, 0)


class Solution:

	def lcs(self, X, Y, n, m):
		global a
		if n == 0 or m == 0:
			return 0
		if a[n][m] != -1:
			return a[n][m]
		if X[n - 1] == Y[m - 1]:
			a[n][m] = 1 + self.lcs(X, Y, n - 1, m - 1)
			return a[n][m]
		else:
			a[n][m] = max(self.lcs(X, Y, n - 1, m), self.lcs(X, Y, n, m - 1))
			return a[n][m]

	def findMinCost(self, X, Y, costX, costY):
		x = len(X)
		y = len(Y)
		global a
		a = []
		for i in range(x + 1):
			col = []
			for j in range(y + 1):
				col.append(-1)
			a.append(col)
		z = self.lcs(X, Y, x, y)
		return costX * (x - z) + costY * (y - z)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		N = len(X)
		M = len(Y)
		dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
		for i in range(1, N + 1):
			dp[i][0] = i * costX
		for j in range(1, M + 1):
			dp[0][j] = j * costY
		for i in range(1, N + 1):
			for j in range(1, M + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(costX + dp[i - 1][j], costY + dp[i][j - 1])
		return dp[N][M]


class Solution:

	def lcs(self, dp, x, y, xIndx, yIndx):
		if xIndx == len(x) and yIndx == len(y):
			return 0
		if xIndx == len(x) or yIndx == len(y):
			return 0
		if dp[xIndx][yIndx] != -1:
			return dp[xIndx][yIndx]
		if x[xIndx] == y[yIndx]:
			dp[xIndx][yIndx] = 1 + self.lcs(dp, x, y, xIndx + 1, yIndx + 1)
			return dp[xIndx][yIndx]
		dp[xIndx][yIndx] = max(self.lcs(dp, x, y, xIndx, yIndx + 1), self.lcs(dp, x, y, xIndx + 1, yIndx))
		return dp[xIndx][yIndx]

	def findMinCost(self, X, Y, costX, costY):
		dp = [[-1] * len(Y) for _ in range(len(X))]
		lcs = self.lcs(dp, X, Y, 0, 0)
		return (len(X) - lcs) * costX + (len(Y) - lcs) * costY


class Solution:

	def findMinCost(self, x, y, costx, costy):
		m = len(x)
		n = len(y)
		dp = [[None for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif x[i - 1] == y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		lcs = dp[m][n]
		cozt = (m - lcs) * costx + (n - lcs) * costy
		return cozt


class Solution:

	def findMinCost(self, s1, s2, c1, c2):
		dp = [[0 for col in range(len(s1) + 1)] for row in range(len(s2) + 1)]
		for col in range(1, len(s1) + 1):
			dp[0][col] = col * c1
		for row in range(1, len(s2) + 1):
			dp[row][0] = row * c2
		for i in range(1, len(dp)):
			for j in range(1, len(dp[0])):
				if s2[i - 1] == s1[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i][j - 1] + c1, dp[i - 1][j] + c2)
		return dp[-1][-1]


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		lenX = len(X)
		lenY = len(Y)
		dp = [[-1 for i in range(lenY + 1)] for j in range(lenX + 1)]
		lcs = self.helper(X, Y, lenX, lenY, dp)
		return (lenX - lcs) * costX + (lenY - lcs) * costY

	def helper(self, X, Y, lenX, lenY, dp):
		if lenX == 0 or lenY == 0:
			return 0
		if dp[lenX][lenY] != -1:
			return dp[lenX][lenY]
		if X[lenX - 1] == Y[lenY - 1]:
			dp[lenX][lenY] = 1 + self.helper(X, Y, lenX - 1, lenY - 1, dp)
			return dp[lenX][lenY]
		else:
			dp[lenX][lenY] = max(self.helper(X, Y, lenX - 1, lenY, dp), self.helper(X, Y, lenX, lenY - 1, dp))
		return dp[lenX][lenY]


class Solution:

	def lcs(self, s1, s2, x, y):
		memo = [[None] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					memo[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					memo[i][j] = 1 + memo[i - 1][j - 1]
				else:
					memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
		return memo[x][y]

	def findMinCost(self, X, Y, costX, costY):
		o = Solution()
		return (len(X) - o.lcs(X, Y, len(X), len(Y))) * costX + (len(Y) - o.lcs(X, Y, len(X), len(Y))) * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		d = [[0] * (n + 1) for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					d[i][j] = 1 + d[i - 1][j - 1]
				else:
					d[i][j] = max(d[i - 1][j], d[i][j - 1])
		t = d[-1][-1]
		tx = costX * (m - t) + costY * (n - t)
		return tx


class Solution:

	def findMinCost(self, s1, s2, x, y):
		dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
		for i in range(len(s1) + 1):
			for j in range(len(s2) + 1):
				if i == 0:
					dp[i][j] = 0 if j == 0 else dp[i][j - 1] + y
				elif j == 0:
					dp[i][j] = x + dp[i - 1][j]
				elif s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i - 1][j] + x, dp[i][j - 1] + y)
		return dp[-1][-1]


class Solution:

	def findMinCost(self, x, y, costX, costY):
		a = []
		for i in range(len(x) + 1):
			lst = []
			for j in range(len(y) + 1):
				lst.append(0)
			a.append(lst)
		for i in range(1, len(x) + 1):
			for j in range(1, len(y) + 1):
				if x[i - 1] == y[j - 1]:
					a[i][j] = 1 + a[i - 1][j - 1]
				else:
					a[i][j] = max(a[i - 1][j], a[i][j - 1])
		mt = a[len(x)][len(y)]
		cost = (len(x) - mt) * costX + (len(y) - mt) * costY
		return cost


def minCost(X, m, Y, n, costX, costY):
	dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
	for x in range(m + 1):
		for y in range(n + 1):
			if x == 0:
				dp[x][y] = y * costY
			elif y == 0:
				dp[x][y] = x * costX
			elif X[x - 1] == Y[y - 1]:
				dp[x][y] = dp[x - 1][y - 1]
			else:
				dp[x][y] = min(dp[x - 1][y] + costX, dp[x][y - 1] + costY)
	return dp[m][n]

class Solution:

	def findMinCost(self, X, Y, costX, costY):
		return minCost(X, len(X), Y, len(Y), costX, costY)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		res = dp[m][n]
		return costX * (m - res) + costY * (n - res)


class Solution:

	def findMinCost(self, s1, s2, cx, cy):
		(m, n) = (len(s1), len(s2))
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, 1 + n):
			for j in range(1, 1 + m):
				if s1[j - 1] == s2[i - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		lcs = dp[-1][-1]
		return cx * (m - lcs) + cy * (n - lcs)


class Solution:

	def lcs(self, X, Y):
		ls = []
		for i in range(len(X) + 1):
			ls.append([0] * (len(Y) + 1))
		for i in range(1, len(X) + 1):
			for j in range(1, len(Y) + 1):
				if X[i - 1] == Y[j - 1]:
					ls[i][j] = ls[i - 1][j - 1] + 1
				else:
					ls[i][j] = max(ls[i - 1][j], ls[i][j - 1])
		return ls[len(X)][len(Y)]

	def findMinCost(self, X, Y, costX, costY):
		fin = self.lcs(X, Y)
		if fin == 0:
			return len(X) * costX + len(Y) * costY
		else:
			return costX * (len(X) - fin) + costY * (len(Y) - fin)


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		a = len(X)
		b = len(Y)
		t = [[0 for i in range(a + 1)] for j in range(b + 1)]
		for i in range(1, b + 1):
			for j in range(1, a + 1):
				if Y[i - 1] == X[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		sub = t[-1][-1]
		z = (len(X) - sub) * costX + (len(Y) - sub) * costY
		return z


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n1 = len(X)
		n2 = len(Y)
		tab = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if X[i - 1] == Y[j - 1]:
					tab[i][j] = 1 + tab[i - 1][j - 1]
				else:
					tab[i][j] = max(tab[i][j - 1], tab[i - 1][j])
		return (n1 - tab[-1][-1]) * costX + (n2 - tab[-1][-1]) * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		d = [[-1 for _ in range(len(Y))] for __ in range(len(X))]
		return self.get(X, Y, costX, costY, 0, 0, d)

	def get(self, s1, s2, costX, costY, i, j, d):
		if len(s1) == i and len(s2) == j:
			return 0
		elif len(s1) == i and j < len(s2):
			return (len(s2) - j) * costY
		elif len(s2) == j and i < len(s1):
			return (len(s1) - i) * costX
		elif d[i][j] != -1:
			return d[i][j]
		elif s1[i] == s2[j]:
			d[i][j] = self.get(s1, s2, costX, costY, i + 1, j + 1, d)
		else:
			d[i][j] = min(costX + self.get(s1, s2, costX, costY, i + 1, j, d), costY + self.get(s1, s2, costX, costY, i, j + 1, d))
		return d[i][j]


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		ans = [[0 for i in range(m + 1)] for i in range(n + 1)]
		for i in range(0, n + 1):
			for j in range(0, m + 1):
				if i == 0 or j == 0:
					ans[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					ans[i][j] = ans[i - 1][j - 1] + 1
				else:
					ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
		x1 = costX * (n - ans[n][m]) if n > ans[n][m] else 0
		x2 = costY * (m - ans[n][m]) if m > ans[n][m] else 0
		return x1 + x2


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		costX = int(costX)
		costY = int(costY)
		n = len(X)
		m = len(Y)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] += dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		lcs = dp[-1][-1]
		return (n - lcs) * costX + (m - lcs) * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		K = [[0 for x in range(n + 1)] for x in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					K[i][j] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					K[i][j] = 1 + K[i - 1][j - 1]
				else:
					K[i][j] = max(K[i - 1][j], K[i][j - 1])
		return costX * (m - K[m][n]) + costY * (n - K[m][n])


class Solution:

	def findMinCost(self, a1, b1, costX, costY):
		n1 = len(a1)
		n2 = len(b1)
		memo = [[0 for x in range(n2 + 1)] for x in range(n1 + 1)]
		for i in range(n1, -1, -1):
			for j in range(n2, -1, -1):
				if i == n1 and j == n2:
					memo[i][j] = 0
				elif i == n1:
					memo[i][j] = 0
				elif j == n2:
					memo[i][j] = 0
				elif a1[i] == b1[j]:
					memo[i][j] = 1 + memo[i + 1][j + 1]
				else:
					memo[i][j] = max(memo[i + 1][j], memo[i][j + 1])
		temp = memo[0][0]
		return (n1 - temp) * costX + (n2 - temp) * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		x = len(X)
		y = len(Y)
		dp = [[0] * (y + 1) for i in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == 0 or j == 0:
					dp[i][j] = 0
				elif X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return (x - dp[x][y]) * costX + (y - dp[x][y]) * costY


class Solution:

	def findMinCost(self, s1, s2, costX, costY):
		m = len(s1)
		n = len(s2)
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			dp[i][0] = dp[i - 1][0] + costX
		for j in range(1, n + 1):
			dp[0][j] = dp[0][j - 1] + costY
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1]
				else:
					dp[i][j] = min(dp[i - 1][j] + costX, dp[i][j - 1] + costY)
		return dp[m][n]


class Solution:

	def lcs(self, s1, s2):
		(n1, n2) = (len(s1), len(s2))
		mt = [[0 for i in range(n1 + 1)] for j in range(n2 + 1)]
		for i in range(1, n2 + 1):
			for j in range(1, n1 + 1):
				if s1[j - 1] == s2[i - 1]:
					mt[i][j] = 1 + mt[i - 1][j - 1]
				else:
					mt[i][j] = max(mt[i - 1][j], mt[i][j - 1])
		return mt[-1][-1]

	def findMinCost(self, s1, s2, c1, c2):
		k = self.lcs(s1, s2)
		return c1 * (len(s1) - k) + c2 * (len(s2) - k)


class Solution:

	def findMinCost(self, x, y, costX, costY):
		n = len(x)
		m = len(y)
		t = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if x[i - 1] == y[j - 1]:
					t[i][j] = 1 + t[i - 1][j - 1]
				else:
					t[i][j] = max(t[i - 1][j], t[i][j - 1])
		return (n - t[-1][-1]) * costX + (m - t[-1][-1]) * costY


class Solution:

	def findMinCost(self, s1, s2, costX, costY):
		m = len(s1)
		n = len(s2)
		lcs = 0
		table = [[0 for i in range(n + 1)] for i in range(m + 1)]
		table[0][0] = 0
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					table[i][j] = 1 + table[i - 1][j - 1]
				else:
					table[i][j] = max(table[i - 1][j], table[i][j - 1])
		return (m - table[m][n]) * costX + (n - table[m][n]) * costY


class Solution:

	def findMinCost(self, s1, s2, c1, c2):
		n = len(s1)
		m = len(s2)
		r = n - m
		dp = [[0 for i in range(m + 1)] for j in range(1 + n)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		r1 = n - dp[n][m]
		r2 = m - dp[n][m]
		return r1 * c1 + r2 * c2


class Solution:

	def findMinCost(self, X, Y, cX, cY):
		d = [[0 for i in range(len(Y))] for j in range(len(X))]
		c = Solution.delt(self, X, Y, cX, cY, len(X), len(Y), d)
		return d[len(X) - 1][len(Y) - 1]

	def delt(self, X, Y, r, s, a, b, d):
		if a == 0 and b == 0:
			return 0
		elif a == 0:
			return b * s
		elif b == 0:
			return a * r
		if X[0] == Y[0]:
			if d[a - 1][b - 1] == 0:
				d[a - 1][b - 1] = Solution.delt(self, X[1:], Y[1:], r, s, a - 1, b - 1, d)
			return d[a - 1][b - 1]
		else:
			if d[a - 1][b - 1] == 0:
				d[a - 1][b - 1] = min(r + Solution.delt(self, X[1:], Y, r, s, a - 1, b, d), s + Solution.delt(self, X, Y[1:], r, s, a, b - 1, d))
			return d[a - 1][b - 1]


class Solution:

	def findMinCost1(self, x, y, costx, costy):
		if x == y:
			return 0
		if len(x) == 0:
			return len(y) * costy
		if len(y) == 0:
			return len(x) * costx
		if x[0] == y[0]:
			return self.findMinCost1(x[1:], y[1:], costx, costy)
		return min(costx + self.findMinCost1(x[1:], y, costx, costy), costy + self.findMinCost1(x, y[1:], costx, costy))

	def get_lcs_len(self, x, y):
		(lenx, leny) = (len(x), len(y))
		dp = [[0] * (leny + 1) for _ in range(lenx + 1)]
		for i in range(1, lenx + 1):
			for j in range(1, leny + 1):
				if x[i - 1] == y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[lenx][leny]

	def findMinCost(self, x, y, costx, costy):
		lcs_len = self.get_lcs_len(x, y)
		return costx * (len(x) - lcs_len) + costy * (len(y) - lcs_len)


class Solution:

	def findMinCost(self, X, Y, costX, costY):

		def LCS(X, Y):
			dp = [[0 for i in range(len(X) + 1)] for j in range(len(Y) + 1)]
			for i in range(len(Y) - 1, -1, -1):
				for j in range(len(X) - 1, -1, -1):
					if Y[i] == X[j]:
						dp[i][j] = 1 + dp[i + 1][j + 1]
					else:
						dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
			return dp[0][0]
		s1 = len(X) - LCS(X, Y)
		s2 = len(Y) - LCS(X, Y)
		return s1 * costX + s2 * costY


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		dp = []
		l1 = len(X)
		l2 = len(Y)
		for i in range(l1 + 1):
			a = [0] * (l2 + 1)
			dp.append(a)
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		left = l1 - dp[l1][l2]
		right = l2 - dp[l1][l2]
		res = left * costX + right * costY
		return res


import numpy as np

class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		t = np.empty((n + 1, m + 1), dtype=int)
		for i in range(n + 1):
			t[i][0] = 0
		for j in range(m + 1):
			t[0][j] = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if X[i - 1] == Y[j - 1]:
					t[i][j] = t[i - 1][j - 1] + 1
				else:
					t[i][j] = max(t[i][j - 1], t[i - 1][j])
		res = (n - t[n][m]) * costX + (m - t[n][m]) * costY
		return res


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		n = len(X)
		m = len(Y)
		li = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[j - 1] == Y[i - 1]:
					li[i][j] = li[i - 1][j - 1] + 1
				else:
					li[i][j] = max(li[i - 1][j], li[i][j - 1])
		a = li[m][n]
		return costX * (n - a) + costY * (m - a)


class Solution:

	def lcs(self, x, y, s1, s2):
		arr = [[0] * (y + 1) for i in range(x + 1)]
		for i in range(x):
			for j in range(y):
				if s1[i] != s2[j]:
					arr[i + 1][j + 1] = max(arr[i + 1][j], arr[i][j + 1])
				else:
					arr[i + 1][j + 1] = arr[i][j] + 1
		return arr[x][y]

	def findMinCost(self, X, Y, costX, costY):
		noc = self.lcs(len(X), len(Y), X, Y)
		total_cost = costX * (len(X) - noc) + costY * (len(Y) - noc)
		return total_cost


class Solution:

	def findMinCost(self, x, y, costx, costy):
		(m, n) = (len(x), len(y))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if x[i - 1] == y[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
		return (m - dp[m][n]) * costx + (n - dp[m][n]) * costy


class Solution:

	def findMinCost(self, s1, s2, x, y):
		n = len(s1)
		m = len(s2)
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[j - 1] == s2[i - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return x * (n - dp[m][n]) + y * (m - dp[m][n])


class Solution:

	def findMinCost(self, X, Y, costX, costY):
		m = len(X)
		n = len(Y)
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if X[i - 1] == Y[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
		l = dp[-1][-1]
		delX = m - l
		delY = n - l
		return delX * costX + delY * costY