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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\n# code by RAJ BHAVSAR\nimport sys\ndef get_ints(): return map(int, sys.stdin.readline().strip().split())\ndef get_list(): return list(map(int, sys.stdin.readline().strip().split()))\ndef get_string(): return sys.stdin.readline().strip()\n\ndef row_helper(data,s,p,q):\n t1 = 0\n for i in range(len(data[0])):\n  if(data[0][i] != int(s[i])):\n   t1 += min(p,q)\n return t1\n\ndef col_helper(data,s,p,q):\n t1 = 0\n for i in range(len(data)):\n  if(data[i][0] != int(s[i])):\n   t1 += min(p,q)\n return t1\n\nfor _ in range(int(input())):\n row,col = get_ints()\n data = []\n for i in range(row):\n  data.append(get_list())\n s = get_string()\n p,q = get_ints()\n if(row == 1):\n  print(row_helper(data,s,p,q))\n else:\n  if(col == 1):\n   print(col_helper(data,s,p,q))\n  else:\n   ans = 0\n   i = 0\n   while(i < row):\n    temp = []\n    x,y = i,0\n    while(x >= 0 and y < col):\n     temp.append(data[x][y])\n     x -= 1\n     y += 1\n    t1 = 0\n    for l in temp:\n     if(l != int(s[i])):\n      t1 += p\n    t2 = q\n    for l in temp:\n     if(l == int(s[i])):\n      t2 += p\n    ans += min(t1,t2)\n    i += 1\n   loop = i\n   i -= 1\n   j = 1\n   while(j < col):\n    temp = []\n    x,y = i,j\n    while(y < col and x >= 0):\n     temp.append(data[x][y])\n     y += 1\n     x -= 1\n    t1 = 0\n    for l in temp:\n     if(l != int(s[loop])):\n      t1 += p\n    t2 = q\n    for l in temp:\n     if(l == int(s[loop])):\n      t2 += p\n    ans += min(t1,t2)\n    j += 1\n    loop += 1\n   print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14639