#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <numeric>
#include <deque>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <fstream>
#include <bitset>
#include <ctime>
#include <cstdio>
#include <chrono>
#include <functional>
using namespace std;
#define int long long
#ifdef LOCAL
bool local = true;
#else
bool local = false;
#endif
/*<-------DEFINES START------->*/
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define for1(n) for (int i = 1; i < n; ++i)
#define for0(n) for (int i = 0; i < n; ++i)
#define rep(i, j, n) for (int i = (j); i < (n); ++i)
#define rrep(i, j, n) for (int i = (j); i >= (n); --i)
#define debug(fmt, ...) \
fprintf(stderr, "[%d] " fmt "\n", LINE, ##__VA_ARGS__)
#define re return
#define con continue
#define pb push_back
#define pob pop_back;
#define sz(x) (int)size(x)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<long long>;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvll = vector<vector<long long>>;
using vpii = vector<pair<long long, long long>>;
using vvpii = vector<vpii>;
/*<-------DEFINES END------->*/
/*<-------TEMPLATES START------->*/
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
for (T& i : a) in >> i;
return in;
}
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& a) {
in >> a.fi >> a.se;
return in;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2>& a) {
out << a.fi << " " << a.se;
return out;
}
template<typename T1, typename T2> istream& operator>>(istream& in, vector<pair<T1, T2>>& a) {
for (pair<T1, T2>& i : a)
in >> i.fi >> i.se;
return in;
}
template<typename T> ostream& operator<<(ostream& out, const vector<T>& a) {
for (auto i : a) {
out << i << " ";
}
return out;
}
template<typename T1, typename T2> ostream& operator<<(ostream& out, vector<pair<T1, T2>>& a) {
for (pair<T1, T2> i : a)
out << i.fi << " " << i.se << endl;
return out;
}
template<typename T1> ostream& operator<<(ostream& out, vector<vector<T1>>& a) {
for (vector<T1> i : a) {
for (T1 j : i) out << j << " ";
out << endl;
}
return out;
}
template<typename T1, typename T2> inline T1 min(T1 a, T2 b) {
b = (T1)b;
return a > b ? b : a;
}
template<typename T1, typename T2> inline T1 max(T1 a, T2 b) {
b = (T1)b;
return a > b ? a : b;
}
template<typename T1, typename T2> inline void amin(T1& a, T2 b) {
a = min(a, b);
}
template<typename T1, typename T2> inline void amax(T1& a, T2 b) {
a = max(a, b);
}
/*<-------TEMPLATES END------->*/
double getTime() {
return clock() / (double)CLOCKS_PER_SEC;
}
int randint(int start, int end) {
return rand() % (end - start + 1) + start;
}
ll gcd(ll a, ll b) {
if (a == 0) {
return b;
}
return gcd(b % a, a);
}
ll gcd(ll a, ll b, ll& x, ll& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
ll x1, y1, g = gcd(b % a, a, x1, y1);
// (b % a) * x1 + a * y1 = g
// a * x + b * y = g
x = y1 - (b / a * x1);
y = x1;
return g;
}
ll bin_pow(ll a, ll b, ll MOD) {
if (b == 0) {
return 1 % MOD;
}
if (b % 2 == 0) {
ll p = bin_pow(a, b / 2, MOD) % MOD;
return p * p % MOD;
}
return a * bin_pow(a, b - 1, MOD) % MOD;
}
void solve();
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (local) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int tt = 1;
// cin >> tt;
rep(i, 1, tt + 1) {
if (local) {
cout << "Case #" << i << ":\n";
}
solve();
}
if (local) {
cout << "\n";
cout << "Time = " << getTime() << " ms\n";
}
return 0;
}
/*<-------ACTUAL CODE STARTS HERE------->*/
const int INF = 2e18, MAXN = 2e5 + 1000, MOD = 1e9 + 7, kk = 13;
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
random_device rd;
mt19937 rnd(rd());
int n, m;
int get(int x, int y) {
re x * m + y;
}
const int N = 500;
vi gr[N] {};
int used[N] {}, st[N] {};
map<array<int, 4>, int> edges;
void dfs(int u, int p, int& cnt, int& proverka) {
used[u] = 1;
cnt++;
for (int v : gr[u]) {
if (v != p) {
if (!used[v]) {
dfs(v, u, cnt, proverka);
} else {
proverka = 1;
}
}
}
}
map<tuple<multiset<int>, multiset<int>, int>, int> mp;
int f(multiset<int>& s1, multiset<int>& s2, int cur_h) {
if (s1.empty() && s2.empty()) re 0;
if (mp.find({s1, s2, cur_h}) != mp.end()) re mp[{s1, s2, cur_h}];
int ans = INF;
if (!s1.empty()) {
int sz2 = *s1.begin();
s1.erase(s1.begin());
if (!cur_h) {
ans = f(s1, s2, 1) - sz2;
if (sz2 > 2) amin(ans, f(s1, s2, 0) - (sz2 - 2) + 2);
} else {
ans = f(s1, s2, 0) + sz2;
if (sz2 > 2) amax(ans, f(s1, s2, 1) + (sz2 - 2) - 2);
}
s1.insert(sz2);
}
if (!s2.empty()) {
int sz4 = *s2.begin();
s2.erase(s2.begin());
if (!cur_h) {
int cand = f(s1, s2, 1) - sz4;
if (sz4 >= 4) amin(cand, f(s1, s2, 0) - (sz4 - 4) + 4);
if (ans != INF) amax(ans, cand);
else ans = cand;
} else {
int cand = f(s1, s2, 0) + sz4;
if (sz4 >= 4) amax(cand, f(s1, s2, 1) + (sz4 - 4) - 4);
if (ans != INF) amin(ans, cand);
else ans = cand;
}
s2.insert(sz4);
}
mp[{s1, s2, cur_h}] = ans;
re ans;
}
void solve() {
cin >> n >> m;
rep(i, 0, n + 1) {
string s; cin >> s;
rep(j, 0, m) {
if (s[j] == '0') {
edges[{i, j, i, j + 1}] = 1;
edges[{i, j + 1, i, j}] = 1;
}
}
}
rep(i, 0, n) {
string s; cin >> s;
rep(j, 0, m + 1) {
if (s[j] == '0') {
edges[{i, j, i + 1, j}] = 1;
edges[{i + 1, j, i, j}] = 1;
}
}
}
rep(i, 1, n + 1) {
rep(j, 1, m + 1) {
st[get(i, j)] += edges[{i, j, i, j - 1}];
st[get(i, j)] += edges[{i, j, i - 1, j}];
st[get(i, j)] += edges[{i - 1, j, i - 1, j - 1}];
st[get(i, j)] += edges[{i, j - 1, i - 1, j - 1}];
if (i < n && edges[{i, j, i, j - 1}]) {
gr[get(i, j)].pb(get(i + 1, j));
}
if (j < m && edges[{i, j, i - 1, j}]) {
gr[get(i, j)].pb(get(i, j + 1));
}
if (i > 1 && edges[{i - 1, j - 1, i - 1, j}]) {
gr[get(i, j)].pb(get(i - 1, j));
}
if (j > 1 && edges[{i, j - 1, i - 1, j - 1}]) {
gr[get(i, j)].pb(get(i, j - 1));
}
if (!st[get(i, j)]) {
used[get(i, j)] = 1;
}
}
}
vpii cmps;
multiset<int> s1, s2;
rep(i, 1, n + 1) {
rep(j, 1, m + 1) {
int cnt = 0;
if (!used[get(i, j)]) {
int proverka = 0;
dfs(get(i, j), -1, cnt, proverka);
if (!proverka) {
s1.insert(cnt);
} else {
s2.insert(cnt);
}
}
}
}
cout << f(s1, s2, 0) << "\n";
}
