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: interview

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()


# cook your dish here
# code by RAJ BHAVSAR
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))
 else:
  if(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)

# cook your dish here
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)


# cook your dish here
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)

# cook your dish here
t=int(input())
while(t):
 n,m=map(int, input().split())
 a=[]
 for i in range(n):
  a.append(list(map(int, input().split())))
 # print(a)
 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

# cook your dish here
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)









#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
#import io,os; input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline #for     pypy
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)