Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

﻿﻿Chef loves single-colored squares, so he got a rectangular board with size $N \times M$ consisting only of black cells and white cells. He calculates the *cost* of the board in the following manner:
Let's denote the number of ways to choose $k^{2}$ white cells which form a square with edge length $k$ (and edges parallel to the borders of the board) by $W_{k}$. For example, a $2 \times 3$ board consisting of 6 white cells and no black cells has $W_{1}=6$, $W_{2}=2$ and $W_{3}=0$. 
Similarly, let's denote the number of ways to choose $k^{2}$ black cells forming a square by $B_{k}$.
Chef chose two sequences of non-negative integers $C_{W}$ and $C_{B}$, each with length $\mathrm{min}(N, M)$. The cost of the board is defined as
$$\sum_{i=1}^{\mathrm{min}(N, M)} C_{B, i} \cdot B_{i} + C_{W, i} \cdot W_{i}\,.$$

However, Chef accidentally spilled some sauce on the board while cooking, so the colors of some cells cannot be determined. Now he wants to repaint each of these cells using black or white paint. What is the maximum achievable cost of the resulting board? Note that he may paint different cells using different colors.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains a string with length $M$ describing the $i$-th row of the board — the character '0' stands for a white cell, '1' stands for a black cell and '?' stands for a cell with unknown color.
The following line contains $K=\mathrm{min}(N, M)$ space-separated integers $C_{W, 1}, C_{W, 2}, \dots, C_{W, K}$.
The last line contains $K=\mathrm{min}(N, M)$ space-separated integers $C_{B, 1}, C_{B, 2}, \dots, C_{B, K}$.

------  Output ------
For each test case, print a single line containing one integer — the maximum possible cost.

------  Constraints  ------
$1 ≤ T ≤ 5$
$1 ≤ N \cdot M ≤ 500$
each string contains only characters '0', '1' and '?'
$0 ≤ C_{W, i} ≤ 10^{8}$ for each valid $i$
$0 ≤ C_{B, i} ≤ 10^{8}$ for each valid $i$

------  Subtasks ------
Subtask #1 (5 points): $1 ≤ N \cdot M ≤ 10$

Subtask #2 (15 points): $1 ≤ N \cdot M ≤ 40$

Subtask #3 (80 points): original constraints

----- Sample Input 1 ------ 
1
3 3
10?
01?
???
1 1 1
2 2 2
----- Sample Output 1 ------ 
18
----- explanation 1 ------ 
Example case 1: Replacing each '?' by '1' gives the optimal answer.

Source: codechef | Difficulty: VERY_HARD
Tags: Flows and cuts


Solutions:
import collections

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		self.g[fr].append([to, cap, len(self.g[to])])
		self.g[to].append([fr, 0, len(self.g[fr]) - 1])

	def add_multi_edge(self, v1, v2, cap1, cap2):
		self.g[v1].append([v2, cap1, len(self.g[v2])])
		self.g[v2].append([v1, cap2, len(self.g[v1]) - 1])

	def bfs(self, s):
		level = [-1] * self.n
		deq = collections.deque()
		level[s] = 0
		deq.append(s)
		while deq:
			v = deq.popleft()
			for e in self.g[v]:
				if e[1] > 0 and level[e[0]] < 0:
					level[e[0]] = level[v] + 1
					deq.append(e[0])
		self.level = level

	def dfs(self, v, t, f):
		if v == t:
			return f
		es = self.g[v]
		level = self.level
		for i in range(self.it[v], len(self.g[v])):
			e = es[i]
			if e[1] > 0 and level[v] < level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.g[e[0]][e[2]][1] += d
					self.it[v] = i
					return d
		self.it[v] = len(self.g[v])
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				break
			self.it = [0] * self.n
			while True:
				f = self.dfs(s, t, 10 ** 9 + 7)
				if f > 0:
					flow += f
				else:
					break
		return flow

def calc(cs, S, N, M):
	tmp = [[0] * M for i in range(N)]
	for i in range(N):
		Si = S[i]
		Ti = tmp[i]
		cnt = 0
		for j in range(M - 1, -1, -1):
			if Si[j] in cs:
				cnt += 1
			else:
				cnt = 0
			Ti[j] = cnt
	D = [[0] * M for i in range(N)]
	for j in range(M):
		st = []
		for i in range(N - 1, -1, -1):
			v = tmp[i][j]
			if v == 0:
				while st:
					st.pop()
				continue
			s = 1
			for (w, k) in reversed(st):
				s = max(s, min(w, k - i + 1))
			D[i][j] = min(v, s)
			l = i
			while st and st[-1][0] >= v:
				l = st.pop()[1]
			if not st or st[-1][0] < v:
				st.append((v, l))
	return D
import random
random.seed()
INF = 10 ** 18
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	K = min(N, M)
	S = [input() for i in range(N)]
	(*CW,) = map(int, input().split())
	(*CB,) = map(int, input().split())
	DW = calc('0?', S, N, M)
	DB = calc('1?', S, N, M)
	su = 0
	for (dw, db) in zip(DW, DB):
		su += sum(dw) + sum(db)
	dinic = Dinic(2 + N * M + su)
	ans = 0
	cnt = 2 + N * M
	for i in range(N):
		for j in range(M):
			for k in range(1, DW[i][j] + 1):
				ans += CW[k - 1]
				p = cnt
				cnt += 1
				dinic.add_edge(0, p, CW[k - 1])
				for x in range(k):
					for y in range(k):
						if S[i + x][j + y] == '?':
							dinic.add_edge(p, 2 + (i + x) * M + j + y, INF)
			for k in range(1, DB[i][j] + 1):
				ans += CB[k - 1]
				q = cnt
				cnt += 1
				dinic.add_edge(q, 1, CB[k - 1])
				for x in range(k):
					for y in range(k):
						if S[i + x][j + y] == '?':
							dinic.add_edge(2 + (i + x) * M + j + y, q, INF)
	print(ans - dinic.max_flow(0, 1))