Home

Contest: Task: Related: TaskF TaskH

Score : $600$ points

Problem Statement

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$-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.

Constraints

  • $1 \leq H, W \leq 100$
  • $-10^9 \leq A_{i, j} \leq 10^9$
  • All values in input are integers.

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}$

Output

Print the answer.

Sample Input 1

2 3
-9 5 1
6 -2 4

Sample Output 1

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 Input 2

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 Output 2

1743