Zeroing the Grid

Time limit7sMemory limit256 MB

Summary

Find the fewest operations that zero the grid when each operation decrements two orthogonally adjacent cells by 1.

Level: Hard8 of 10
Topics: Graph
Solved: No attempts yet

Problem

A grid filled with non-negative integers is given. You can apply the following operation to the grid as many times as you want.

Choose two cells of the grid that are adjacent horizontally or vertically.
For each chosen cell, decrease its value by 1 if that value is positive.

You may choose a cell that already holds 0, and that cell stays 0.

The picture below shows four consecutive operations on a 2×2 grid that turn every number into 0. The two yellow cells are the cells chosen in that step.

In this example four operations turn every number into 0, and no smaller number of operations does.

Write a program that finds the minimum number of operations needed to turn every number of the given grid into 0.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains the number of rows $n$ and the number of columns $m$ of the grid ( $2 \le n, m \le 50$ ). Each of the next $n$ lines contains the $m$ integers of that row of the grid, in column order. Each integer is between $0$ and $1{,}000$ .

Output

For each test case, print the minimum number of operations on its own line.

Examples7

Example 1
Input
```
2
2 2
1 3
1 2
2 4
2 3 2 3
1 2 1 1
```
Expected output
```
4
8
```
Example 2
Input
```
1
2 2
0 0
0 0
```
Expected output
```
0
```
Example 3
Input
```
1
2 2
5 0
0 0
```
Expected output
```
5
```
Example 4
Input
```
1
2 2
7 7
0 0
```
Expected output
```
7
```
Example 5
Input
```
1
2 2
4 0
0 4
```
Expected output
```
8
```
Example 6
Input
```
1
2 2
1000 1000
1000 1000
```
Expected output
```
2000
```
Example 7
Input
```
1
3 3
1 2 3
4 5 6
7 8 9
```
Expected output
```
25
```