Score : $600$ points

问题描述

在一个 $H \times W$ 的网格上，有 $H$ 行和 $W$ 列的卡片。对于每一对整数 $(i, j)$ 满足 $1 \leq i \leq H, 1 \leq j \leq W$，在第 $i$ 行第 $j$ 列的卡片上写有一个整数 $A_{i, j}$。

高桥和青木将合作进行一场游戏，游戏包括以下步骤：

• 首先，高桥选择 $H$ 行中的某些行（可能不选或全选），并在所选行的每张卡片上放置一个红色标记。
• 然后，青木选择 $W$ 列中的某些列（可能不选或全选），并在所选列的每张卡片上放置一个蓝色标记。
• 接下来，他们按照以下方式计算得分：
  • 如果存在带有负整数且同时拥有红色和蓝色标记的卡片，则此次游戏为“完全失败”，得分为 $-10^{100}$。
  • 否则，他们收集所有放置了一个或多个标记的卡片。得分是这些被收集卡片上所写整数之和。

请找出他们的最大可能得分。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:00:23