qwq 实在挑不出来了

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1e4 + 5;
const int maxm = 2e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, S, T, cnt, flow, tlow;
int h[maxn], dis[maxn];
vector<vector<int> > id[4];
vector<int> pv;
bool vis[maxn];

struct edge {
	int to, w, c, nxt;
} e[maxm];

int tot = 1, head[maxn];
inline void add(int u, int v, int w, int c) {
	if(u == S) flow++;
	if(v == T) tlow++;
	e[++tot].to = v;
	e[tot].w = w;
	e[tot].c = c;
	e[tot].nxt = head[u];
	head[u] = tot;

	e[++tot].to = u;
	e[tot].w = 0;
	e[tot].c = -c;
	e[tot].nxt = head[v];
	head[v] = tot;
}

inline void spfa() {
	for(int i = 1; i <= T; i++) h[i] = inf;
	h[S] = 0;
	queue<int> q;
	q.push(S);
	vis[S] = true;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		vis[u] = false;
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if(e[i].w && h[v] > h[u] + e[i].c) {
				h[v] = h[u] + e[i].c;
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
}

struct node {
	int u, w;
	bool operator < (const node& p) const {
		return w > p.w;
	}
} ;

struct pedge {
	int to, e;
} p[maxn];

inline bool dijkstra() {
	for(int i = 1; i <= T; i++) dis[i] = inf, vis[i] = false;
	dis[S] = 0;
	priority_queue<node> q;
	q.push((node){ S, 0 });
	while(!q.empty()) {
		int u = q.top().u; q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to, nc = h[u] + e[i].c - h[v];
			if(e[i].w && dis[v] > dis[u] + nc) {
				dis[v] = dis[u] + nc;
				p[v].to = u;
				p[v].e = i;
				if(!vis[v]) q.push((node){ v, dis[v] });
			}
		}
	}
	return dis[T] != inf;
}

inline int Duel() {
	int maxf = 0, minc = 0;
	spfa();
	while(dijkstra()) {
		int minf = inf;
		for(int i = 1; i <= T; i++) h[i] += dis[i];
		for(int i = T; i != S; i = p[i].to) minf = min(minf, e[p[i].e].w);
		for(int i = T; i != S; i = p[i].to) {
			e[p[i].e].w -= minf;
			e[p[i].e^1].w += minf;
		}
		maxf += minf;
		minc += minf * h[T];
	}
	if(flow != tlow || maxf != flow) return -1;
	else return minc;
}

inline bool black(int x, int y) { return (x&1) ^ (y&1); }

inline int chk(int x) {
	x = (x < 0 ? x+4 : x);
	return x >= 4 ? x-4 : x;
}

int main() {
	scanf("%d %d", &n, &m);
	if(n%10 == 0) putchar('y');

	for(int i = 1; i <= m+1; i++) pv.push_back(0);
	for(int k = 0; k < 4; k++)
	for(int i = 1; i <= n+1; i++) id[k].push_back(pv);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			id[1][i][j] = ++cnt;
			id[2][i][j] = ++cnt;
			if(i > 1) id[0][i][j] = id[2][i-1][j];
			else id[0][i][j] = ++cnt;
			if(j > 1) id[3][i][j] = id[1][i][j-1];
			else id[3][i][j] = ++cnt;
		}
	S = ++cnt; T = ++cnt;

    int x;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			scanf("%d", &x);
            pv.clear();
			for(int k = 0; k < 4; k++) (x>>k & 1) ? pv.push_back(k) : void();
			if(pv.empty()) continue;
			if(pv.size() == 1) {
				if(black(i, j)) add(id[pv[0]][i][j], T, 1, 0), add(id[chk(pv[0]+1)][i][j], id[pv[0]][i][j], 1, 1), add(id[chk(pv[0]-1)][i][j], id[pv[0]][i][j], 1, 1), add(id[chk(pv[0]+2)][i][j], id[pv[0]][i][j], 1, 2);
				else add(S, id[pv[0]][i][j], 1, 0), add(id[pv[0]][i][j], id[chk(pv[0]+1)][i][j], 1, 1), add(id[pv[0]][i][j], id[chk(pv[0]-1)][i][j], 1, 1), add(id[pv[0]][i][j], id[chk(pv[0]+2)][i][j], 1, 2);
			}
			else if(pv.size() == 2) {
				if(pv[1]-pv[0] == 2) {
					if(black(i, j)) add(id[pv[0]][i][j], T, 1, 0), add(id[pv[1]][i][j], T, 1, 0);
					else add(S, id[pv[0]][i][j], 1, 0), add(S, id[pv[1]][i][j], 1, 0);
				}
				else {
					if(pv[1]-pv[0] == 1) swap(pv[0], pv[1]);
					if(black(i, j)) add(id[pv[0]][i][j], T, 1, 0), add(id[pv[1]][i][j], T, 1, 0), add(id[chk(pv[0]+1)][i][j], id[pv[1]][i][j], 1, 1), add(id[chk(pv[0]+2)][i][j], id[pv[0]][i][j], 1, 1);
					else add(S, id[pv[0]][i][j], 1, 0), add(S, id[pv[1]][i][j], 1, 0), add(id[pv[1]][i][j], id[chk(pv[0]+1)][i][j], 1, 1), add(id[pv[0]][i][j], id[chk(pv[0]+2)][i][j], 1, 1);
				}
			}
			else if(pv.size() == 3) {
				x = 1+2+3 - pv[0] - pv[1] - pv[2];
				if(black(i, j)) add(id[pv[0]][i][j], T, 1, 0), add(id[pv[1]][i][j], T, 1, 0), add(id[pv[2]][i][j], T, 1, 0), add(id[x][i][j], id[chk(x+1)][i][j], 1, 1), add(id[x][i][j], id[chk(x-1)][i][j], 1, 1), add(id[x][i][j], id[chk(x+2)][i][j], 1, 2);
				else add(S, id[pv[0]][i][j], 1, 0), add(S, id[pv[1]][i][j], 1, 0), add(S, id[pv[2]][i][j], 1, 0), add(id[chk(x+1)][i][j], id[x][i][j], 1, 1), add(id[chk(x-1)][i][j], id[x][i][j], 1, 1), add(id[chk(x+2)][i][j], id[x][i][j], 1, 2);
			}
			else {
				if(black(i, j)) for(int k = 0; k < 4; k++) add(id[k][i][j], T, 1, 0);
				else for(int k = 0; k < 4; k++) add(S, id[k][i][j], 1, 0);
			}
		}

	printf("%d\n", Duel());
	return 0;
}