Woburn Challenge 1999 - Suicidal

Adam Sandler is now a wedding juicer, i.e. he designs interesting punch-bowl designs. His latest design is as follows: it is built up from a flat board of dimensions ~n \times m~ ~(n, m \le 100)~. Onto the board, he pastes ~n \times m~ solid blocks - each ~1 \times 1~ in width, but with variable heights (height will be integers ~\le 10\,000~), i.e. the entire board is covered with these blocks and no ~2~ blocks are stacked. To determine if this is a feasible design for a wedding, he needs to determine how much punch can fit into this funky punchbowl. So, you might wonder where the juice is going to go if all the blocks are solid. Keep in mind that juice can get trapped between boxes.

You will be given ~n~ and ~m~, followed by a grid of ~n~ rows of ~m~ items (each item separated by ONE space). This grid will contain the heights of the cuboid block at that grid position on the board. Given these numbers, you must output the volume of punch that will fit into the bowl. Assume that there is no surface tension on the board and so an unbounded region can hold no juice.

Input Specification

Line ~1~: Number of input sets
Each input set has the following format:

• ~1^\text{st}~ line: ~n~ ~m~, the height and width of the board
• ~n~ lines each containing ~m~ positive integers, representing the height of the squares of the bowl

Output Specification

For each test case, output the amount of juice the given bowl can hold.

Sample Input

1
4 4
4 4 4 4
4 1 1 4
4 1 1 4
4 4 4 4

Sample Output

12