G - Grid Card Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

H \times W 枚のカードが H 行 W 列のグリッド上に並んでいます。 1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) について、i 行目 j 列目にあるカードには整数 A_{i, j} が書かれています。

高橋君と青木君が 2 人で協力ゲームをします。具体的には、下記の手順を行います。

  • まず、高橋君が H 個の行のうちいくつか（ 0 行でも H 行すべてでも良い）を選び、選んだ行にあるそれぞれのカードの上に赤いトークンを 1 個ずつ置きます。
  • 続いて、青木君が W 個の列のうちいくつか（ 0 列でも W 列すべてでも良い）を選び、選んだ列にあるそれぞれのカードの上に青いトークンを 1 個ずつ置きます。
  • その後、2 人は以下の通りに得点を計算します。
    • もし、負の整数が書かれたカードであって上に赤いトークンと青いトークンがともに置かれているものが 1 枚でも存在するならば、ゲームの結果は「大失敗」となり、得点は -10^{100} 点です。
    • そうでない場合、2 人は上にトークンが 1 個以上置かれているカードをすべて獲得します。獲得したカードに書かれた整数の合計が得点です。

得点としてあり得る最大値を求めてください。

制約

  • 1 \leq H, W \leq 100
  • -10^9 \leq A_{i, j} \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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}

出力

答えを出力せよ。

入力例 1

2 3
-9 5 1
6 -2 4

出力例 1

9

高橋君が 2 行目のみを選び青木君が 3 列目のみを選ぶとき、 2 人は 4 枚のカードを獲得し、得点は 6 + (-2) + 1 + 4 = 9 点となります。 これが考えられる最大値です。

入力例 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

出力例 2

1743

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