当前没有测试数据。

G - 网格卡片游戏

得分: $600$ 分

题目描述

网格上有 $H \times W$ 张卡片，其中 $H$ 行 $W$ 列。 对于每对整数 $(i, j)$ 满足 $1 \leq i \leq H, 1 \leq j \leq W$，编号为第 $i$ 行第 $j$ 列的卡片上写有整数 $A_{i, j}$。

Takahashi 和 Aoki 合作玩一种游戏，游戏包括以下步骤。

• 首先，Takahashi 选择一些行（可能是零行或全部行），并在每个选中行上的每张卡片上放置一个红色令牌。
• 其次，Aoki 选择一些列（可能是零列或全部列），并在每个选中列上的每张卡片上放置一个蓝色令牌。
• 最后，他们按照以下方式计算得分。
  • 如果有一张卡片上有负整数，并且该卡片上同时放有红色和蓝色令牌，那么这次游戏是“完全失败”，得分是 $-10^{100}$。
  • 否则，他们收集所有放置了一个或多个令牌的卡片，得分是这些卡片上整数的总和。

求他们的最大可能得分。

限制

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

输出

输出答案。

2 3
-9 5 1
6 -2 4

9

如果 Takahashi 只选择第 $2$ 行，Aoki 只选择第 $3$ 列，那么他们将收集到四张卡片，得分是 $6 + (-2) + 1 + 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