Binary Board

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef loves singlecolored 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 nonnegative 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 spaceseparated integers $N$ and $M$.  $N$ lines follow. For each $i$ ($1 \le i \le 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)$ spaceseparated integers $C_{W, 1}, C_{W, 2}, \dots, C_{W, K}$.  The last line contains $K=\mathrm{min}(N, M)$ spaceseparated 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 \le T \le 5$  $1 \le N \cdot M \le 500$  each string contains only characters '0', '1' and '?'  $0 \le C_{W, i} \le 10^8$ for each valid $i$  $0 \le C_{B, i} \le 10^8$ for each valid $i$ ### Subtasks **Subtask #1 (5 points):** $1 \le N \cdot M \le 10$ **Subtask #2 (15 points):** $1 \le N \cdot M \le 40$ **Subtask #3 (80 points):** original constraints ### Example Input ``` 1 3 3 10? 01? ??? 1 1 1 2 2 2 ``` ### Example Output ``` 18 ``` ### Explanation **Example case 1:** Replacing each '?' by '1' gives the optimal answer.Author:  ratingoverflow 
Tester:  mgch 
Tags  hard, june18, likecs, minimumcut, ratingoverflow, ratingoverflow 
Date Added:  20052018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 