### Woburn Challenge 1999 - Suicidal

## The Wedding Juicer

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 nxm (m,n ≤ 100). Onto the board, he pastes nxm solid blocks - each 1x1 in width, but with variable heights (height will be integers ≤ 10000), 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

Line 1: Number of input setsEach input set has the following format:

- 1st 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

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

All Submissions

Best Solutions

**Point Value:** 25

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 28, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

SourSpinachon Nov 30, 2008 - 11:41:08 pm UTC Clarificationhansonw1on Nov 11, 2008 - 12:56:34 am UTC RejudgedBryanon Nov 14, 2008 - 12:43:03 am UTC Re: Re: Rejudgedhansonw1on Nov 14, 2008 - 1:07:41 am UTC Partial pointsFor some problems, like Daycare, you get partial marks because there is also the question of efficiency - you can make a correct but slow algorithm. Thus you'll get some points for this, but making it faster is quite difficult, and hence worth more points.

HelloMelloon Nov 10, 2008 - 10:26:06 pm UTC Multiple Spaces?eg.

1

3 5

5 5 5 5 5

5 4 5 1 3

5 5 5 5 5

hansonw1on Nov 10, 2008 - 11:46:56 pm UTC Re: Multiple Spaces?