以下では、\((1, 1)\) から \((H, W)\) へ白いマスのみからなる移動経路を作る最小費用を求めます。 黒いマスのみからなる場合の最小費用も同様の方法で求めることができるので、両者の最小値を本問題の答えとして出力すれば良いです。

まず、操作を複数回行う場合、その順番は結果に影響しません。 また、同じ行（または列）に対して操作を \(2\) 回行うと、その行（または列）の状態は元に戻ります。 よって、私たちが実際に決定するのは、各行と各列について「操作を \(0\) 回行うか \(1\) 回行うか」です。 実は、\(1\) 行目を反転するかを決め、通りたい移動経路 \(1\) つを選ぶと、選んだ経路のすべてのマスを白色にするためにはどの行および列を反転しなければならないかが一意に定まります。

実際にマス \((1, 1)\) から \(1\) マスずつ移動しながら、白いマスのみからなる移動経路を \(1\) つ作ることを考えます。その過程では、反転しなければならないことが確定した行および列を随時反転していきます。 具体的には以下の手順を考えます。

• まず、\(R_1\) 円払って \(1\) 行目を反転しても良い。
• その後、\((1, 1)\) の現在の色が黒なら、\(C_1\) 円払って \(1\) 列目を反転する。
• 次に、マス \((1, 1)\) に立ち、次に進む方向として、右または下の好きな向きを向く。
• 以降、\((H, W)\) に到達するまで以下を繰り返す。
  1. 現在いるマスを \((i, j)\) とし、現在向いている向きに \(1\) マス進んだ先のマスを \((i', j')\) とする。
  2. \((i', j')\) の現在の色が黒ならば、
     • 現在下を向いているなら \(R_{i'}\) 円払って \(i'\) 行目を反転する。
     • 現在右を向いているなら \(C_{j'}\) 円払って \(j'\) 列目を反転する。
  3. \((i, j)\) から \((i', j')\) に移動し、次に進む方向として、右または下の好きな向きを向く。

白いマスのみからなる移動経路を作る最小費用を求めるには、 上記の手順でマス \((H, W)\) に到達までにかかる最小費用を求めれば良いです。 これを動的計画法（ DP ）によって求めます。

DP の状態としては、現在いるマス \((i, j)\) と現在の向き \(d\) に加え、 上記の手順 2. で「 \((i', j')\) の現在の色」を取得するための情報が必要です。\((i', j')\) は以前に行われた \(i'\) 行目または \(j'\) 列目への操作によって、初期状態と比べて色が反転している可能性があります。 \((i', j')\) がすでに反転されているかを知るには、現在向いている行（または列）（すなわち、いま右を向いているなら \(i\) 行目、現在下を向いているなら \(j\) 列目）に対して今までに反転操作を行っているかわかれば十分です。 以上を踏まえて、下記のDP テーブルによる DP を行います。

\(\mathrm{dp}[i][j][d][l] := \)（現在マス \((i, j)\) に \(d (=\) 右 or 下 \()\)の向きで立っており、現在向いている行（または列）に対して \(l (=0\) or \(1)\) 回の操作を行っているときの、現在までにかかった合計費用としてあり得る最小値）

各状態からは、現在の向きに \(1\) マス進んだ後つぎにどちらの向きを向くかという \(2\) つの選択肢に対応した \(2\) 本の遷移を行えば良いです。

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

#include <iostream>
#define inf 1e18
using namespace std;
typedef long long ll;

ll h, w;
ll r[2005], c[2005];
char a[2005][2005];
ll dp[2005][2005][2][2];
ll di[2] = {1, 0}, dj[2] = {0, 1};

ll solve()
{
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++){
    for(int d = 0; d <= 1; d++) for(int f = 0; f <= 1; f++){
      dp[i][j][d][f] = inf;
    }
  }
  for(int r1 = 0; r1 <= 1; r1++){
    int c1 = (a[1][1]^r1);
    dp[1][1][0][c1] = r1*r[1] + c1*c[1];
    dp[1][1][1][r1] = r1*r[1] + c1*c[1];
  }
  
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      for(int d = 0; d <= 1; d++){
        for(int l = 0; l <= 1; l++){
          int ni = i + di[d], nj = j + dj[d];
          if(ni > h || nj > w) continue;
          
          int flip = a[ni][nj]^l, cost = 0;
          if(d == 0) cost = r[ni]*flip;
          else cost = c[nj]*flip;
          
          for(int nd = 0; nd <= 1; nd++){
            int nl = l;
            if(d != nd) nl = flip;
            dp[ni][nj][nd][nl] = min(dp[ni][nj][nd][nl], dp[i][j][d][l] + cost);
          }
        }
      }
    }
  }

  ll ret = inf;
  for(int d = 0; d <= 1; d++) for(int f = 0; f <= 1; f++) ret = min(ret, dp[h][w][d][f]);
  return ret;
}

int main(void)
{
  cin >> h >> w;
  for(int i = 1; i <= h; i++) cin >> r[i];
  for(int i = 1; i <= w; i++) cin >> c[i];
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> a[i][j], a[i][j] -= '0';

  ll ans = solve();
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) a[i][j] ^= 1;
  ans = min(ans, solve());
  cout << ans << endl;

  return 0;
}