You are organizing an international dancing competition. You have already obtained all of the following:
- A dance floor with rows and columns, consisting of unit square cells;
- competitors;
- A cutting-edge automated judge for the competition.
But you are still missing an audience! You are worried that the competition might not be interesting enough, so you have come up with a way to calculate the interest level for the competition.
Each competitor occupies one square unit cell of the floor and stays there until they are eliminated. A compass neighbor of a competitor is another competitor chosen such that shares a row or column with , and there are no competitors still standing in cells in between and . Each competitor may have between and compass neighbors, inclusive, and the number may decrease if all the other competitors in one orthogonal direction are eliminated.
The competition runs one round at a time. In between rounds and , if a competitor had at least one compass neighbor during round , and 's skill level is strictly less than the average skill level of all of 's compass neighbors, is eliminated and is not part of the competition for rounds etc. Notice that still counts as a neighbor of their other compass neighbors for the purpose of other eliminations that may also happen between rounds and . Competitors that do not have any compass neighbors are never eliminated. If after a round no competitor is eliminated, then the competition ends.
The interest level of a round is the sum of skill levels of the competitors dancing in that round (even any competitors that are to be eliminated between that round and the next). The interest level of the competition is the sum of the interest levels of all of the rounds.
Given the skill levels of the dancers that are on the floor for the first round, what is the interest level of the competition?
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing two integers and . Then, there are more lines containing integers each. The -th value on the of these lines, , represents the skill level of the dancer in the cell in the row and column of the floor.
Output Specification
For each test case, output one line containing Case #x: y
, where is the test case number (starting from ) and is the interest level of the competition.
Limits
Time limit: 40 seconds per test set.
Memory limit: 1 GB.
, for all and .
Test Set 1
.
.
Test Set 2
.
, in exactly cases.
, in exactly cases.
Sample Input
4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3
Sample Output
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14
In Sample Case #1, only one competitor is on the floor. Since the competitor does not have any compass neighbors, they dance in one round, and then the competition is over. Thus the answer is equal to the dancer's skill level, .
In Sample Case #2, the interest level of the first round is .
The competitors that are not in the center nor in a corner have a skill level of , but the average of their compass neighbors is , which is greater than , so they are eliminated. The floor during the second round looks like this:
1 . 1
. 2 .
1 . 1
This round is the last one. The competitors in the corner have two compass neighbors each, but the average of their skill level is equal to their own. The competitor in the center has no compass neighbor. The interest level of the round is . This means the interest level of the competition is .
In Sample Case #3, the competitor with skill level is eliminated after the first round, while the other two remain. In the second round, the two other competitors become compass neighbors, and this causes the competitor with skill level to be eliminated. There is a single competitor in the third round, which makes it the last one. The interest levels of the rounds are and , making the interest level of the competition .
Comments