Given $N *M$ matrix containing elements either $1$ or $0$ and string S of length $N+M-1$ containing characters $0$ or $1$. Your task is to make all the  paths from top left corner to the  bottom right corner of the matrix same as the  given string .You can perform two types of operations any time .Path means you can only allow it to take right or down. 
Operations :
- Changing the matrix elements from $1$ to $0$ or vice versa  will cost P rupees per element.
- Changing the character of string  from $1$ to $0$ or vice versa  will cost Q rupees per character.
You have to  minimize the cost, (possibly 0) .

-----Input:-----
- First line of input contains the total no. of test cases $T$. 
- For every test case, first line of input contains two spaced positive integers, $N$ and $M$.
- Next $N$ lines contains $M$-spaced integers which can be only $0$ or $1$.
- Next line of input contains a string $S$ of length $N+M-1$.
- Last line of input contains two spaced integers, $P$ and $Q$.

-----Output:-----
- $You$ $have$ $to$ $print$ $the$ $minimum$ $cost .$

-----Constraints-----
- $1 \leq T \leq 20$
- $1 \leq N, M \leq 1000$
- $|S| = N+M-1$
- $0 \leq P, Q \leq 1000$The input/output is quite large, please use fast reading and writing methods.

-----Sample Input-----
2
3 3
1 0 1
0 1 1
1 1 0
10111
10 5
3 3 
0 0 1
0 1 1
0 1 1
00011
2 9

-----Sample Output-----
5
4

-----Explanation-----
- You can  change the last element of the matrix and also can change the last element of string but the minimum cost will produce by changing string element , therefore it will cost 5 rupees.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import stdin, stdout
import math, bisect
from collections import Counter, deque, defaultdict
L = lambda : list(map(int, stdin.readline().strip().split()))
M = lambda : list(map(int, stdin.readline().strip().split()))
I = lambda : int(stdin.readline().strip())
S = lambda : stdin.readline().strip()
C = lambda : stdin.readline().strip().split()

def pr(a):
	return ' '.join(list(map(str, a)))

def solve():
	(n, m) = M()
	a = []
	for i in range(n):
		a += [L()]
	s = S()
	(p, q) = M()
	ans = [[0, 0] for i in range(n + m)]
	for i in range(n):
		for j in range(m):
			if a[i][j] == 0:
				ans[i + j][0] += 1
			else:
				ans[i + j][1] += 1
	c = 0
	for i in range(n + m - 1):
		(A, B, C, D) = (0, 0, 0, 0)
		if s[i] == '0':
			A = ans[i][1] * p
			B = q + ans[i][0] * p
			c += min(A, B)
		else:
			C = ans[i][0] * p
			D = q + ans[i][1] * p
			c += min(C, D)
	print(c)
for _ in range(I()):
	solve()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def row_helper(data, s, p, q):
	t1 = 0
	for i in range(len(data[0])):
		if data[0][i] != int(s[i]):
			t1 += min(p, q)
	return t1

def col_helper(data, s, p, q):
	t1 = 0
	for i in range(len(data)):
		if data[i][0] != int(s[i]):
			t1 += min(p, q)
	return t1
for _ in range(int(input())):
	(row, col) = get_ints()
	data = []
	for i in range(row):
		data.append(get_list())
	s = get_string()
	(p, q) = get_ints()
	if row == 1:
		print(row_helper(data, s, p, q))
	elif col == 1:
		print(col_helper(data, s, p, q))
	else:
		ans = 0
		i = 0
		while i < row:
			temp = []
			(x, y) = (i, 0)
			while x >= 0 and y < col:
				temp.append(data[x][y])
				x -= 1
				y += 1
			t1 = 0
			for l in temp:
				if l != int(s[i]):
					t1 += p
			t2 = q
			for l in temp:
				if l == int(s[i]):
					t2 += p
			ans += min(t1, t2)
			i += 1
		loop = i
		i -= 1
		j = 1
		while j < col:
			temp = []
			(x, y) = (i, j)
			while y < col and x >= 0:
				temp.append(data[x][y])
				y += 1
				x -= 1
			t1 = 0
			for l in temp:
				if l != int(s[loop]):
					t1 += p
			t2 = q
			for l in temp:
				if l == int(s[loop]):
					t2 += p
			ans += min(t1, t2)
			j += 1
			loop += 1
		print(ans)


import math
read = lambda : list(map(int, input().strip().split()))
read_arr = lambda x: [read() for _ in range(x)]
ans = []
t = int(input().strip())

def mincost(n, m, arr, s, p, q):
	cost = 0
	for t in range(n + m - 1):
		cc = s[t]
		curr = 0
		ct = 0
		start = max(0, t - (m - 1))
		end = min(n, t + 1)
		for i in range(start, end):
			j = t - i
			if j >= m:
				break
			curr += cc ^ arr[i][j]
			ct += 1
		cost1 = q + (ct - curr) * p
		cost2 = curr * p
		cost += min(cost1, cost2)
	return cost
for i in range(t):
	(cn, cm) = read()
	carr = read_arr(cn)
	cs = [int(x) for x in input().strip()]
	(cp, cq) = read()
	ans.append(mincost(cn, cm, carr, cs, cp, cq))
print('\n'.join([str(x) for x in ans]))


from sys import *
input = stdin.readline
for u in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	s = input()
	(x, y) = list(map(int, input().split()))
	d = [0] * len(s)
	k = [0] * len(s)
	for i in range(n):
		for j in range(m):
			if str(l[i][j]) != s[(i + j) % (n + m - 1)]:
				d[(i + j) % (n + m - 1)] += 1
			k[i + j] += 1
	c = 0
	for i in range(len(s)):
		c += min(d[i] * x, y + (k[i] - d[i]) * x)
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ml = []
	for i in range(n):
		ml.append(list(map(int, input().split())))
	s = input()
	(p, q) = map(int, input().split())
	nl = [0] * (n + m - 1)
	pl = [0] * (n + m - 1)
	for i in range(n):
		for j in range(m):
			if ml[i][j] != int(s[i + j]):
				nl[i + j] += 1
			else:
				pl[i + j] += 1
	c = 0
	for i in range(len(nl)):
		c += min(nl[i] * p, pl[i] * p + q)
	print(c)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	s = input()
	(p, q) = map(int, input().split())
	a0 = []
	a1 = []
	for i in range(n + m - 1):
		a0.append(0)
		a1.append(0)
	for i in range(n):
		for j in range(m):
			if a[i][j] == 0:
				a0[i + j] += 1
			else:
				a1[i + j] += 1
	cost = 0
	for i in range(len(s)):
		if s[i] == '0':
			cost += min(p * a1[i], p * a0[i] + q)
		else:
			cost += min(p * a0[i], p * a1[i] + q)
	print(cost)
	t -= 1


import sys
from collections import defaultdict

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	c = []
	(n, m) = get_ints()
	d0 = defaultdict(int)
	d1 = defaultdict(int)
	for _ in range(n):
		a = get_array()
		c.append(a)
	s = input()
	(p, q) = list(map(int, input().split()))
	for i in range(n):
		for j in range(m):
			if c[i][j] == 0:
				d0[i + j] += 1
			else:
				d1[i + j] += 1
	su = 0
	case1 = '0'
	case2 = '1'
	for i in range(len(s)):
		x = d0[i]
		y = d1[i]
		if s[i] == '0':
			cost1 = y * p
			cost2 = q + x * p
		if s[i] == '1':
			cost1 = y * p + q
			cost2 = x * p
		su += min(cost1, cost2)
	print(su)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
for _ in range(inp()):
	(n, m) = ip()
	x = [ip() for i in range(n)]
	s = input().strip()
	(p, q) = ip()
	ans = 0
	for i in range(n + m - 1):
		dt = {0: 0, 1: 0}
		if i < m:
			(row, col) = (0, i)
		else:
			(row, col) = (i - m + 1, m - 1)
		while col >= 0 and row < n:
			dt[x[row][col]] += 1
			col -= 1
			row += 1
		if s[i] == '0':
			t = min(dt[1] * p, q + dt[0] * p)
		elif s[i] == '1':
			t = min(dt[0] * p, q + dt[1] * p)
		ans += t
	print(ans)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = [input().split() for _ in range(n)]
	s = input()
	(p, q) = list(map(int, input().split()))
	t = 0
	for (i, j) in enumerate(s):
		c = 0
		if i >= m:
			x = i - m + 1
			y = m - 1
		else:
			x = 0
			y = i
		f = 0
		while 0 <= x < n and 0 <= y < m:
			c += a[x][y] != j
			f += 1
			x += 1
			y -= 1
		t += min(c * p, p * (f - c) + q)
	print(t)


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	l = []
	for i in range(a):
		l.append(list(map(int, input().split())))
	k = []
	for i in range(b):
		x = 0
		y = 0
		(n, m) = (0, i)
		while n < a and m >= 0:
			if l[n][m] == 0:
				x += 1
			else:
				y += 1
			n += 1
			m -= 1
		k.append([x, y])
	for i in range(1, a):
		x = 0
		y = 0
		(n, m) = (i, b - 1)
		while n < a and m >= 0:
			if l[n][m] == 0:
				x += 1
			else:
				y += 1
			n += 1
			m -= 1
		k.append([x, y])
	ans = 0
	s = input()
	(p, q) = list(map(int, input().split()))
	for i in range(a + b - 1):
		if s[i] == '0':
			ans += min(k[i][1] * p, q + k[i][0] * p)
		else:
			ans += min(k[i][0] * p, q + k[i][1] * p)
	print(ans)