If both choose no columns (or rows), then the score is \(0\), so the optimal score cannot be negative. Especially, the “total failure” is not the optimal solution. Thus, we may forbid a selection that causes the total failure, that is, placing two tokens on a card with a negative integer written on it.

We boil down this problem to a minimum cut problem on a network. The original problem involves both positive scores due to cards with positive integers and negative scores due to cards with negative integers, so we cannot directly boil it down to a minimum cut problem. Instead, let us first consider the state where all the cards with positive integers are collected and minimize the deduction. That is, starting from the state where you have gained the sum \(\Sigma^{+}\) of all positive integers written on the cards, calculate the deduction from the state.

• First, if a card (at the \(i\)-th row and \(j\)-th column) with a positive integer written on it is not finally collected, that is, if Takahashi did not choose the \(i\)-th row and Aoki did not choose the \(j\)-th column, then there will be a deduction of \(A_{i, j}\) points.

• Next, if a card (at the \(i\)-th row and \(j\)-th column) with a negative integer written on it is finally collected, that is, either if Takahashi chose the \(i\)-th row or if Aoki chose the \(i\)-th column, then there will be a deduction of \(A_{i, j}\) points. Therefore,

  • For \(i = 1, 2, \ldots, H\), let \(\Sigma^{-}_{R_i}\) be the sum of absolute values of negative integers written on the cards in the \(i\)-th row. If Takahashi chooses the \(i\)-th row, then there will be a deduction of \(\Sigma^{-}_{R_i}\) points.
  • For \(j = 1, 2, \ldots, W\), let \(\Sigma^{-}_{C_j}\) be the sum of absolute values of negative integers written on the cards in the \(j\)-th column, then there will be a deduction of \(\Sigma^{-}_{C_j}\) points.

Since the “total failure” is forbidden, the deduction due to a single card with a negative integer is never accounted twice by Takahashi’s choice on rows and Aoki’s choice on columns.

As a whole, the problem can be rephrased as follows.

• First, a score of \(\Sigma^{+}\) points is unconditionally gained.
• For \(i = 1, 2, \ldots, H\), if Takahashi chooses the \(i\)-th row, then there is a deduction of \( \Sigma^{-}_{R_i}\) points
• For \(j = 1, 2, \ldots, W\), if Aoki chooses the \(j\)-th column, then there is a deduction of \( \Sigma^{-}_{C_i}\) points
• For each integer pair \((i, j)\) such that \(1 \leq i \leq H, 1 \leq j \leq W\),
  • If \(A_{i, j} \gt 0\): if Takahashi doesn’t choose the \(i\)-th row and Aoki doesn’t choose the \(j\)-th column, then there will be a deduction of \(A_{i, j}\) points
  • If \(A_{i, j} \lt 0\): it is forbidden that “Takahashi chooses the \(i\)-th row and Aoki chooses the \(j\)-th row” is forbidden (there will be a deduction of \(\infity\) points)

This can be represented by the following graph (flow network). The answer can be obtained as \(\Sigma^{+}\) subtracted by “the capacity of the minimum \(S\) - \(T\) cut of the graph below.”

• The graph has Vertices \(R_1, R_2, \ldots, R_H\) corresponding to each row, Vertices \(C_1, C_2, \ldots, C_W\) to each column, a source \(S\), and a sink \(T\) for a total of \((H+W+2)\) vertices.
• For each \(i = 1, 2, \ldots, H\), add an edge from Vertex \(S\) to Vertex \(R_i\) with capacity \(\Sigma^{-}_{R_i}\).
• For each \(j = 1, 2, \ldots, W\), add an edge from Vertex \(C_j\) to Vertex \(T\) with capacity \(\Sigma^{-}_{C_j}\).
• For each integer pair \((i, j)\) such that \(1 \leq i \leq H, 1 \leq j \leq W\), add an edge as follows:
  • If \(A_{i, j} \gt 0\): add an edge from Vertex \(R_i\) to Vertex \(C_j\) with capacity \(A_{i, j}\).
  • If \(A_{i, j} \lt 0\): add an edge from Vertex \(C_i\) to Vertex \(R_j\) with capacity \(\infty\).

We can use Dinic’s algorithm to find the minimum cut of the graph above to solve the problem in a total of \(\mathrm{O}(N^4)\) time.

A sample code in C++ language follows.

#include <iostream>
#include <atcoder/maxflow>
using namespace std;
typedef long long ll;
const ll inf = 1e18;

int h, w;
ll a[105][105];
ll rsum[105], csum[105];

int main(void)
{
  cin >> h >> w;
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> a[i][j];

  atcoder::mf_graph<ll> g(h+w+2);
  int S = 0, T = h+w+1; ll ans = 0;
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      if(a[i][j] >= 0) g.add_edge(i, h+j, a[i][j]), ans += a[i][j];
      else g.add_edge(h+j, i, inf), rsum[i] -= a[i][j], csum[j] -= a[i][j];
    }
  }
  for(int i = 1; i <= h; i++) g.add_edge(S, i, rsum[i]);
  for(int j = 1; j <= w; j++) g.add_edge(h+j, T, csum[j]);
  cout << ans - g.flow(S, T) << endl;

  return 0;
}