Table Covering

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef's friend Aayan loves Ghariyals (those longmouthed crocodile like creatures). Chef's other friend, Mr. KG, knows about this love of Aayan's. So one day, he gives Aayan an interesting problem:
Mr. KG gives Aayan a table A of N rows and M columns filled with nonnegative integers. The rows and colums of the table are indexed starting from 1. A[i][j] denotes the j'th integer in the i'th row of A.
Let's consider some sequence (i_{1}, j_{1}), (i_{2}, j_{2}), ..., (i_{K}, j_{K})(1 ≤ K) of the table cells.
A sequence of table cells is said to be a valid Ghariyalpath if all of the following conditions holds:
 (i_{1}, j_{1}) equals to (1, 1)  the topleft cell of the table
 (i_{K}, j_{K}) equals to (N, M)  the bottomright cell of the table
 i_{t} ≤ i_{t + 1} for each integer 1 ≤ t < K
 j_{t} ≤ j_{t + 1} for each integer 1 ≤ t < K
 i_{t + 1}  i_{t} + j_{t + 1}  j_{t} = 1 for each integer 1 ≤ t < K
One can easily prove that the length of any valid Ghariyalpath is exactly N + M  1 cells. It's also easy to prove that any valid Ghariyalpath contains any of the table cells at most once.
Mr. KG asked Aayan to cover the given table with valid Ghariyalpaths. To be precise, his task is to find the minimal number of valid Ghariyalpaths such that for any table cell with coordinates (i, j) the following condition is satisfied: at least A[i][j] valid Ghariyalpaths contain the (i, j)cell.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and M. The next N lines contain M nonnegative integers each denoting the given table A.
Output
For each test case, output a single line containing the minimal number of valid Ghariyalpaths to cover the table as described above.
Constraints
 1 ≤ T ≤ 10
 0 ≤ A[i][j] ≤ 1000
 Subtask 1(20 points): 1 ≤ N ≤ 20
 Subtask 2(30 points): 1 ≤ N ≤ 100
 Subtask 3(50 points): 1 ≤ N ≤ 1000
Note
The first test of the first subtask is the example test. It's made for you to make sure, that your solution produces the same verdict both on your machine and our server.
Time Limits
Time limit for the first subtask is 2 s. Time limit for the second and the third subtasks is 3 s.
Example
Input: 2 5 4 1 1 1 1 1 2 1 1 1 1 3 1 1 1 1 4 1 1 1 1 2 3 1 2 3 4 5 6 Output: 6 8
Explanation of the example test
In the first case, the following set of valid Ghariyalpaths is one of the optimal ones:
In the second case, the following set of valid Ghariyalpaths is one of the optimal ones:
Author:  kostya_by 
Tester:  pavel1996 
Editorial  http://discuss.codechef.com/problems/TABLECOV 
Tags  dilworth, dynamicprogramming, kostya_by, ltime32, maxflow, partialorder 
Date Added:  27122015 
Time Limit:  2  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions