\(2\) 人ともどの行（または列）も選ばなければ得点は \(0\) になるので、最適解が少なくとも負となることはありません。特に、大失敗が最適解となることはありません。 よって、大失敗となるような選択、すなわち、負の整数が書かれた \(1\) 枚のカードに \(2\) つのトークンが置かれるような選択は、以下ではゲームのルール上禁止としても問題ありません。

ネットワークの最小カット問題に帰着して本問題を解きます。 元の問題のままでは、正の整数のカードによる加点と負の整数のカードによる減点が混在していて最小カット問題に落とし込むことができません。 そこで、まず正の整数が書かれたカードのみをすべて獲得した状態を基準とし、その状態からの減点を出来るだけ少なくする問題とみなします。 つまり、カードに書かれたすべての正の整数の和 \(\Sigma^{+}\) だけの得点をあらかじめ持った状態から始め、その状態からの減点を計算していきます。

• まず、正の数が書かれたカード（ \(i\) 行目 \(j\) 列目にあるとする）について、そのカードを最終的に獲得できなかった場合、すなわち、高橋君が \(i\) 行目を選ばず、かつ、青木君も \(j\) 列目を選ばなかった場合、\(A_{i, j}\) 点の減点になります。

• 次に、負の数が書かれたカード（ \(i\) 行目 \(j\) 列目にあるとする）について、 そのカードを最終的に獲得した場合、すなわち、高橋君が \(i\) 行目を選んだ、または、青木君が \(j\) 列目を選んだ場合、\(A_{i, j}\) の絶対値の分だけ減点になります。 よって、

  • \(i = 1, 2, \ldots, H\) について、\(i\) 行目にあるカードに書かれたすべての負の整数の絶対値の和を \(\Sigma^{-}_{R_i}\) とおくとき、 高橋君が \(i\) 行目を選ぶと \(\Sigma^{-}_{R_i}\) 点の減点になります。
  • 同様に、\(j = 1, 2, \ldots, W\) について、\(j\) 列目にあるカードに書かれたすべての負の整数の絶対値の和を \(\Sigma^{-}_{C_j}\) とおくとき、青木君が \(j\) 行目を選ぶと \(\Sigma^{-}_{C_j}\) 点の減点になります。

大失敗となるような選択は禁止されていることから、負の整数が書かれた \(1\) 枚のカードによる減点が、高橋君による行の選択と青木君による列の選択によって \(2\) 回重複して勘定されることはないことに注意してください。

まとめると、本問題は下記の問題設定に言い換えられます。

• まず無条件で、\(\Sigma^{+}\) 点加点される。
• \(i = 1, 2, \ldots, H\) について、高橋君が \(i\) 行目を選ぶと \( \Sigma^{-}_{R_i}\) 点の減点
• \(j = 1, 2, \ldots, W\) について、青木君が \(j\) 列目を選ぶと \( \Sigma^{-}_{C_i}\) 点の減点
• \(1 \leq i \leq H, 1 \leq j \leq W\) を満たす整数の組 \((i, j)\) について、
  • \(A_{i, j} \gt 0\) のとき：高橋君が \(i\) 行目を選ばず、かつ、青木君も \(j\) 行目を選ばない場合、\(A_{i, j}\) 点の減点
  • \(A_{i, j} \lt 0\) のとき：「高橋君が \(i\) 行目を選び、かつ、青木君も \(j\) 行目を選ぶ」という選択は禁止（ \(\infty\) 点の減点）

これは下記のグラフ（フローネットワーク）で表現することができます。\(\Sigma^{+}\) から「下記のグラフの最小 \(S\) - \(T\) カットの容量」を引いた値として、本問題の答えが得られます。

• 各行に対応する頂点 \(R_1, R_2, \ldots, R_H\) 、各列に対応する頂点 \(C_1, C_2, \ldots, C_W\) 、および始点 \(S\) と終点 \(T\) の合計 \((H+W+2)\) 個の頂点を持つ。
• \(i = 1, 2, \ldots, H\) について、頂点 \(S\) から頂点 \(R_i\) に容量 \(\Sigma^{-}_{R_i}\) の辺を張る。
• \(j = 1, 2, \ldots, W\) について、頂点 \(C_j\) から頂点 \(T\) に容量 \(\Sigma^{-}_{C_j}\) の辺を張る。
• \(1 \leq i \leq H, 1 \leq j \leq W\) を満たす整数の組 \((i, j)\) について次の通りに辺を張る。
  • \(A_{i, j} \gt 0\) のとき：頂点 \(R_i\) から頂点 \(C_j\) に容量 \(A_{i, j}\) の辺を張る。
  • \(A_{i, j} \lt 0\) のとき：頂点 \(C_j\) から頂点 \(R_i\) に容量 \(\infty\) の辺を張る。

上記の最小カットの容量を求めるのに Dinic 法を用いると、本問題を \(\mathrm{O}(N^4)\) 時間で解くことができます。

C++ 言語による正解例を以下に記載します。

#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;
}