Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden on 2012-06-14 19:35:33 by :D

BYTESH - HOSTAGES

no tags 

 

Loki and his army have taken a number of human prisoners. Thankfully, however, Captain America has located where he’s keeping them. There are m rows of prison cells with each row having n cells. There are different number of hostages in every cell which Thor now knows about because he’s got Iron Man helping him.
Captain America plans to help everyone escape but Iron Man, or Stark (one of the brilliant minds of our age), noticed that Loki has wired each of the cells with explosives and it’s very difficult to defuse these bombs. Even if they do manage to open one of the cells, every cell in the row directly above and below it gets blown and the people in those die. The cells immediately to the left and right also get blown. Since it’s now clear that there’s no way that they can save everyone, Captain America has to figure out the maximum number of people he can save and then he keeps on opening doors until there are no more prisoners he can save.



The Description bellow illustrates this, step by step. Each cell represents one prison cell and the number of
hostages it contains. At each step, the chosen box is circled and the shaded cells represent the
cells that will get blown by explosives. After eight steps,his job is over and Captain America managed to save 10 + 9 + 8 +
3 + 7 + 6 + 10 + 1 = 54 people.

 

Description

1   8    2    1    9

1   7    3    5    2

1   2   10   3    18

8  4     7   9      2

7  4     1   3      1

If we select 10 from 3rd row inthird column , entire 2nd row , 4th row become zero , and 3rd row column 2, 3rd row 4th column also become 0;

Matrix after this selection becomes :

1  8  2  1  9

0  0  0  0  0

1  0 10 0 18

0  0  0  0  0

7  4  1  3  1


Input
The input contains several test cases. The first line of a test case contains two positive integers
M and N (1 ≤ M × N ≤ 105), separated by a single space, indicating the number of rows and
columns respectively. Each of the following M lines contains N integers separated by single spaces, each representing the initial number of hostages in the cell. Each cell will
have initially at least 1 and at most 103 hostages.
The end of input is indicated by a line containing two zeroes separated by a single space.

Output
For each test case in the input, your program must print a single line, containing a single value,
the integer indicating the maximum number of hostages that can be freed.
The output must be written to standard output.
Sample input
5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0
Output
54
40
17

 

 


hide comments
:D: 2012-06-14 17:34:58



I'm very sorry, but the problem is already in classical set: SAMER08C

This one will be closed.

Pandian: 2012-05-31 06:30:39

Really nice problem :) Enjoyed doing it :)


Added by:Troika::Bytes
Date:2012-02-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All