真偽値変数 \(X_i\) を、行 \(i\) を選ぶとき True、選ばないとき False とします。
真偽値変数 \(Y_j\) を、列 \(j\) を選ぶとき True、選ばないとき False とします。

このとき、各マスに書かれた数 \(A_{i,j}\) の得点への寄与 \(f_{i,j}(X_i,Y_j)\) は下表のようになります。

求めるものは \(X_i,Y_j\) を適切に定めたときの \(\sum_{i,j}f_{i,j}(X_i,Y_j)\) の最大値です。符号を反転し、\(\sum_{i,j}-f_{i,j}(X_i,Y_j)\) の最小化問題だと思うことにします。 ここで、任意の \(i,j\) で \((X,Y)\mapsto -f_{i,j}(X,\lnot Y)\) は劣モジュラ関数なので、以下の参考文献に基づき機械的にグラフを構築し、最大流を求めることで元の問題に答えることができます。

参考文献：燃やす埋める問題と劣モジュラ関数のグラフ表現可能性 その② グラフ構築編 (theory_and_me さんのブログ)