# -*- coding: utf-8 -*- """ Created on Wed Apr 28 08:59:11 2021 No1479_2.py @author: onodera """ MAX_V = 500*2+2 class Edge: def __init__(self, r, f, t, c): self.rev = r self.fr = f self.to = t self.cap = self.icap = c def __str__(self): if self.cap > 0: return str(self.fr) + "->" + str(self.to) + '(' + str(self.cap) + ')' else: return "" class Graph: def __init__(self, n=0): self.init(n) def init(self, n=0): self.V = n self.l = [[] for _ in range(MAX_V)] def resize(self, n=0): self.V = n def reset(self): for i in range(self.V): for j in range(len(self.l[i])): self.l[i][j].cap = self.l[i][j].icap def get(self, i): return self.l[i] def redge(self, e): if e.fr != e.to: return self.l[e.to][e.rev] else: return self.l[e.to][e.rev+1] def addedge(self, fr, to, cap): self.l[fr].append(Edge(len(self.l[to]), fr, to, cap)) self.l[to].append(Edge(len(self.l[fr]) - 1, to, fr, 0)) def __str__(self): s = '' for l in self.l: for e in l: s += str(e) + '\n' return s level = [0] * MAX_V it = [0] * MAX_V def dibfs(G, s): global it, lecel for i in range(MAX_V): level[i] = -1 level[s] = 0 que = [s] while len(que) > 0: v = que.pop(0) for i in range(len(G.get(v))): e = G.get(v)[i] if level[e.to] < 0 and e.cap > 0: level[e.to] = level[v] + 1 que.append(e.to) def didfs(G, v, t, f): global it, lecel if v == t: return f for i in range(it[v], len(G.get(v))): e = G.get(v)[i] re = G.redge(e) if level[v] < level[e.to] and e.cap > 0: d = didfs(G, e.to, t, min(f, e.cap)) if d > 0: e.cap -= d re.cap += d return d return 0 def Dinic(G, s, t): global it, level res = 0 while True: dibfs(G, s) if level[t] < 0: return res it = [0] * MAX_V flow = didfs(G, s, t, float('inf')) while flow > 0: res += flow flow = didfs(G, s, t, float('inf')) def matches(h, w, edges): G = Graph(h + w + 2) S_node = h + w T_node = h + w + 1 for v in range(h): for u in edges[v]: G.addedge(v, u + h, 1) G.addedge(S_node, v, 1) for u in range(w): G.addedge(u + h, T_node, 1) res = Dinic(G, S_node, T_node) matched = [-1] * w for i in range(h): for e in G.get(i): if e.icap == 1 and e.cap == 0: matched[e.to - h] = i return matched def mpc(xn, yn): global edges matched = matches(xn, yn, edges) left = xn right = 0 ledges = [] redges = matched for v in range(xn): if v not in matched: left -= 1 ledges.append(v) for v in ledges: for u in edges[v]: right += 1 if redges[u] >= 0: left -= 1 return left + right if __name__ == '__main__': H, W = map(int, input().split()) S = dict() for i in range(H): for j, a in enumerate(list(map(int, input().split()))): if a > 0: if a not in S: S[a] = [set(), set()] S[a].append((i, j)) S[a][0].add(i) S[a][1].add(j) cnt = 0 for a, pairs in S.items(): hl = list(pairs[0]) wl = list(pairs[1]) h = len(hl) w = len(wl) edges = [set() for _ in range(h)] for i, j in pairs[2:]: edges[hl.index(i)].add(wl.index(j)) n = mpc(h, w) cnt += n print(cnt)