9639: ABC259 —— G - Grid Card Game
[Creator : ]
Description
There are $H \times W$ cards on a grid of squares with $H$ rows and $W$ columns. For each pair of integers $(i, j)$ such that $1 \leq i \leq H, 1 \leq j \leq W$, the card at the $i$-th row and $j$### Constraints
- $1 \leq H, W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- All values in input are integers.
-th column has an integer $A_{i, j}$ written on it.
Takahashi and Aoki will cooperate to play a game, which consists of the following steps.
- First, Takahashi chooses some of the $H$ rows (possibly none or all) and places a red token on each card in the chosen rows.
- Second, Aoki chooses some of the $W$ columns (possibly none or all) and places a blue token on each card in the chosen columns.
- Now, they compute their score as follows.
- If there is a card with a negative integer that has both red and blue tokens placed on it, the play is a "total failure"; the score is $-10^{100}$.
- Otherwise, they collect all cards that have one or more tokens placed on them. The score is the sum of the integers written on the collected cards.
Find their maximum possible score.
- $1 \leq H, W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- All values in input are integers.
-th column has an integer $A_{i, j}$ written on it.
Takahashi and Aoki will cooperate to play a game, which consists of the following steps.
- First, Takahashi chooses some of the $H$ rows (possibly none or all) and places a red token on each card in the chosen rows.
- Second, Aoki chooses some of the $W$ columns (possibly none or all) and places a blue token on each card in the chosen columns.
- Now, they compute their score as follows.
- If there is a card with a negative integer that has both red and blue tokens placed on it, the play is a "total failure"; the score is $-10^{100}$.
- Otherwise, they collect all cards that have one or more tokens placed on them. The score is the sum of the integers written on the collected cards.
Find their maximum possible score.
Input
Input is given from Standard Input in the following format:
```
$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$
```
```
$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$
```
Output
Print the answer.
Constraints
- $1 \leq H, W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- All values in input are integers.
- $-10^9 \leq A_{i, j} \leq 10^9$
- All values in input are integers.
Sample 1 Input
2 3
-9 5 1
6 -2 4
Sample 1 Output
9
If Takahashi chooses just the 2-nd row and Aoki chooses just the 3-rd column, they collect four cards, for a score of 6+(−2)+1+4=9. This is the maximum possible.
Sample 2 Input
15 20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16
14 31 43 -73 49 -7 -65 13 -40 -45 36 88 -54 -43 99 87 -94 57 -22 31
-85 67 -46 23 95 68 55 17 -56 51 -38 64 32 -19 65 -62 76 66 -53 -16
35 -78 -41 35 -51 -85 24 -22 45 -53 82 -30 39 19 -52 -3 -11 -67 -33 71
-75 45 -80 -42 -31 94 59 -58 39 -26 -94 -60 98 -1 21 25 0 -86 37 4
-41 66 -53 -55 55 98 23 33 -3 -27 7 -53 -64 68 -33 -8 -99 -15 50 40
66 53 -65 5 -49 81 45 1 33 19 0 20 -46 -82 14 -15 -13 -65 68 -65
50 -66 63 -71 84 51 -91 45 100 76 -7 -55 45 -72 18 40 -42 73 69 -36
59 -65 -30 89 -10 43 7 72 93 -70 23 86 81 16 25 -63 73 16 34 -62
22 -88 27 -69 82 -54 -92 32 -72 -95 28 -25 28 -55 97 87 91 17 21 -95
62 39 -65 -16 -84 51 62 -44 -60 -70 8 69 -7 74 79 -12 62 -86 6 -60
-72 -6 -79 -28 39 -42 -80 -17 -95 -28 -66 66 36 86 -68 91 -23 70 58 2
-19 -20 77 0 65 -94 -30 76 55 57 -8 59 -43 -6 -15 -83 8 29 16 34
79 40 86 -92 88 -70 -94 -21 50 -3 -42 -35 -79 91 96 -87 -93 -6 46 27
-94 -49 71 37 91 47 97 1 21 32 -100 -4 -78 -47 -36 -84 -61 86 -51 -9
Sample 2 Output
1743