{"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$\\-th column has an integer $A_{i, j}$ written on it.\nTakahashi and Aoki will cooperate to play a game, which consists of the following steps.\n\n*   First, Takahashi chooses some of the $H$ rows (possibly none or all) and places a red token on each card in the chosen rows.\n*   Second, Aoki chooses some of the $W$ columns (possibly none or all) and places a blue token on each card in the chosen columns.\n*   Now, they compute their score as follows.\n    *   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}$.\n    *   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.\n\nFind their maximum possible score.\n\n## Constraints\n\n*   $1 \\leq H, W \\leq 100$\n*   $-10^9 \\leq A_{i, j} \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$\n$A_{1, 1}$ $A_{1, 2}$ $\\ldots$ $A_{1, W}$\n$A_{2, 1}$ $A_{2, 2}$ $\\ldots$ $A_{2, W}$\n$\\vdots$\n$A_{H, 1}$ $A_{H, 2}$ $\\ldots$ $A_{H, W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc259_g","tags":[],"sample_group":[["2 3\n-9 5 1\n6 -2 4","9\n\nIf 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."],["15 20\n-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16\n14 31 43 -73 49 -7 -65 13 -40 -45 36 88 -54 -43 99 87 -94 57 -22 31\n-85 67 -46 23 95 68 55 17 -56 51 -38 64 32 -19 65 -62 76 66 -53 -16\n35 -78 -41 35 -51 -85 24 -22 45 -53 82 -30 39 19 -52 -3 -11 -67 -33 71\n-75 45 -80 -42 -31 94 59 -58 39 -26 -94 -60 98 -1 21 25 0 -86 37 4\n-41 66 -53 -55 55 98 23 33 -3 -27 7 -53 -64 68 -33 -8 -99 -15 50 40\n66 53 -65 5 -49 81 45 1 33 19 0 20 -46 -82 14 -15 -13 -65 68 -65\n50 -66 63 -71 84 51 -91 45 100 76 -7 -55 45 -72 18 40 -42 73 69 -36\n59 -65 -30 89 -10 43 7 72 93 -70 23 86 81 16 25 -63 73 16 34 -62\n22 -88 27 -69 82 -54 -92 32 -72 -95 28 -25 28 -55 97 87 91 17 21 -95\n62 39 -65 -16 -84 51 62 -44 -60 -70 8 69 -7 74 79 -12 62 -86 6 -60\n-72 -6 -79 -28 39 -42 -80 -17 -95 -28 -66 66 36 86 -68 91 -23 70 58 2\n-19 -20 77 0 65 -94 -30 76 55 57 -8 59 -43 -6 -15 -83 8 29 16 34\n79 40 86 -92 88 -70 -94 -21 50 -3 -42 -35 -79 91 96 -87 -93 -6 46 27\n-94 -49 71 37 91 47 97 1 21 32 -100 -4 -78 -47 -36 -84 -61 86 -51 -9","1743"]],"created_at":"2026-03-03 11:01:14"}}