题目描述

$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$ 個以上置かれているカードをすべて獲得します。獲得したカードに書かれた整数の合計が得点です。

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

输入格式

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

$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 \times W$ 的正方形网格，$i$ 行 $j$ 列的点的权值为 $a_{i,j}$。

• 芷萱选择 $H$ 行中的任意几行（可能为 $0$），给这些行上的点放上一张红色卡片。

• 诺丝选择 $W$ 列中的任意几列（可能为 $0$），给这些列上的点放上一张蓝色卡片。

他们计算本游戏分数的方式如下：

如果存在一个网格 $(i,j)$ 满足 $a_{i,j}<0$ 且这个点上同时存在两种颜色的卡片，则游戏失败，分数为 $-10100$ 分，否则，分数为所有放了卡片（不管放了几张，不管放了什么颜色）的网格的权值之和。

Translated by Tx_Lcy

2 3
-9 5 1
6 -2 4

9

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

1743

提示

制約

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

Sample Explanation 1

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