Grid Card Game

AtCoder

IDabc259_g

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

2 3
-9 5 1
6 -2 4

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.

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Grid Card Game",
    "description": {
      "content": "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$\\-t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc259_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$\\-t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments