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 long-mouthed 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 non-negative 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 (i1, j1), (i2, j2), ..., (iK, jK)(1 ≤ K) of the table cells.
A sequence of table cells is said to be a valid Ghariyal-path if all of the following conditions holds:
- (i1, j1) equals to (1, 1) - the top-left cell of the table
- (iK, jK) equals to (N, M) - the bottom-right cell of the table
- it ≤ it + 1 for each integer 1 ≤ t < K
- jt ≤ jt + 1 for each integer 1 ≤ t < K
- |it + 1 - it| + |jt + 1 - jt| = 1 for each integer 1 ≤ t < K
One can easily prove that the length of any valid Ghariyal-path is exactly N + M - 1 cells. It's also easy to prove that any valid Ghariyal-path contains any of the table cells at most once.
Mr. KG asked Aayan to cover the given table with valid Ghariyal-paths. To be precise, his task is to find the minimal number of valid Ghariyal-paths such that for any table cell with coordinates (i, j) the following condition is satisfied: at least A[i][j] valid Ghariyal-paths contain the (i, j)-cell.
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 non-negative integers each denoting the given table A.
For each test case, output a single line containing the minimal number of valid Ghariyal-paths to cover the table as described above.
- 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
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 limit for the first subtask is 2 s. Time limit for the second and the third subtasks is 3 s.
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 Ghariyal-paths is one of the optimal ones:
In the second case, the following set of valid Ghariyal-paths is one of the optimal ones:
|Tags||dilworth, dynamic-programming, kostya_by, ltime32, maxflow, partial-order|
|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|
Fetching successful submissions