In this editorial, we find the minimum cost to obtain a path from \((1, 1)\) to \((H, W)\) consisting only of white squares. The path consisting of black squares can be found in the same way; print the smaller value as the answer for this problem.

First, the order of multiple operations does not affect the result. Additionally, performing the operation on the same row (or column) twice restores the original state. Therefore, all we have to determine is “whether we perform the operation \(0\) times or once” on each column and row. In fact, if we determine whether to invert the first column and a path, it is uniquely determined which rows and columns should be inverted in order to make all the square on the path white.

Consider constructing a path consisting of white squares starting from Square \((1, 1)\) and moving one square by one, while inverting the rows and columns as necessary. Specifically, consider the following procedures:

• First, we may pay \(R_1\) yen to invert the \(1\)-st row.
• Then, if the current color of \((1, 1)\) is black, then pay \(C_1\) yen to invert the \(1\)-st row.
• Next, stand on Square \((1, 1)\) and face right or down on your choice.
• Repeat the following steps until reaching \((H, W)\):
  1. Let \((i, j)\) be the current square and \((i', j')\) be one square ahead on the direction you are facing.
  2. If \((i', j')\) is painted black,
     • If you are currently facing down, pay \(R_{i'}\) yen to invert the \(i'\)-th row.
     • If you are currently facing right, pay \(C_{j'}\) yen to invert the \(j'\)-th column.
  3. Move from \((i, j)\) to \((i', j')\) and face right or down on your choice.

In order to find the minimum cost to obtain a path consisting of white squares, it is sufficient to find the minimum cost to reach \((H, W)\) by the procedures above. We find this by Dynamic Programming (DP).

What we need as the states of the DP is the current square \((i, j)\), the current direction \((i', j')\), as well as the information to obtain the 2current color of \((i', j')\) in step 2. Whether \((i', j')\) is already inverted can be determined by whether you already inverted the row (or column) you are currently facing (that is, the \(i\)-th row if you are facing right, or the \(j\)-th column if you are facing down). Therefore, we perform the following DP on the following DP table.

\(\mathrm{dp}[i][j][d][l] := \) (the minimum total cost paid so far when you are currently standing on Square \((i, j)\) facing \(d (=\) right or down \()\) and when you have applied an operation \(l (=0\) or \(1)\) times on the row (or column) you are facing).

From each state, two transitions are possible depending on which direction you face after advancing one square ahead in the current direction you are facing.

The following is a sample code in 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;
}