制約から，\(O(HW)\) は間に合う． よって，今いるマスを全探索は可能なので， それで DP を考える．
追加で持っておきたい情報として， 今いる行と列が，それぞれ flip しているか \(in 2 \times 2\) がある．
今居るマスと flip の情報で十分であることが分かる． 実際，これらが分かっていれば，遷移したあとに行，列を flip すべきかどうかは確定する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll h,w; cin >> h >> w;
vll r(h); cinv(r);
vll c(w); cinv(c);
rep(x,h) rep(y,w) s[x][y] -= '0';
ll ans = INFL;
rep(f,2){
vvvll dp(h, vvll(w, vll(4, INFL)));
rep(t,4) {
ll i = t & 1;
ll j = (t >> 1) & 1;
if(s[0][0]^i^j == f){
dp[0][0][t] = i*r[0] + j*c[0];
}
}
rep(x,h) rep(y,w) rep(t,4){
ll i = t & 1;
ll j = (t >> 1) & 1;
ll now = dp[x][y][t];
ll nt, ni, nj;
if(x+1 < h) {
ni = (s[x+1][y] ^ j ^ f);
nt = ni | (j << 1);
chmin(dp[x+1][y][nt], now + r[x+1]*ni);
}
if(y+1 < w){
nj = (s[x][y+1] ^ i ^ f);
nt = i | (nj << 1);
chmin(dp[x][y+1][nt], now + c[y+1]*nj);
}
}
rep(t,4){
chmin(ans, dp[h-1][w-1][t]);
}
}
cout << ans << endl;
return 0;
}
