class BipartiteMatching: def __init__(self): self.len_Y = 0 self.edges = [[]] def add_edge(self, x, y): """ :param x: 頂点集合 X の要素 :param y: 頂点集合 Y の要素 """ while x>=len(self.edges): self.edges.append([]) self.len_Y=max(self.len_Y,y+1) self.edges[x].append(y) def dfs(self,start): """ :param x: X側の未マッチングの頂点の1つ :param visited: 空のsetを渡す(外部からの呼び出し時) :return: 増大路が見つかればTrue """ parents_y=dict() parents_x=dict() x=start next_set=[x] while next_set: x=next_set.pop() for y in self.edges[x]: if y in parents_y: continue if self.matched[y]!=-1: next_x=self.matched[y] next_set.append(next_x) parents_y[y]=x parents_x[next_x]=y else: while x!=start: self.matched[y]=x y=parents_x[x] x=parents_y[y] self.matched[y]=x return 1 return 0 def solve(self): """ 最大マッチング数を返す """ self.matched = [-1] * self.len_Y # matched[y]=x: 最大マッチングを考えた時の y とペアの x self.len_X=len(self.edges) self.visited = set() res = 0 for x in range(self.len_X): self.visited = set() res += self.dfs(x) return res class MinimumVertexCover: def __init__(self): self.BM=BipartiteMatching() def add_edge(self, x, y): self.BM.add_edge(x,y) def solve(self): BM=self.BM BM.solve() len_X,len_Y=BM.len_X,BM.len_Y edges=BM.edges matched=BM.matched Xc,Y=[1]*len_X,[0]*len_Y for x in range(len_X): tmp_X=[x] tmp_Y=[] for y in edges[x]: if matched[y]==x: break if matched[y]!=-1: tmp_X.append(matched[y]) tmp_Y.append(y) else: for x in tmp_X: Xc[x]=0 for y in tmp_Y: Y[y]=1 res_X,res_Y=[],[] for x in range(len_X): if Xc[x]==1: res_X.append(x) for y in range(len_Y): if Y[y]==1: res_Y.append(y) res_X.sort() res_Y.sort() return res_X,res_Y ################################################################################################# def example(): global input example = iter( """ 6 6 8 1 1 2 2 2 4 2 5 3 6 4 3 5 3 6 6 """ .strip().split("\n")) input = lambda: next(example) ################################################################################################# import sys input = sys.stdin.readline from collections import defaultdict H,W=map(int, input().split()) d=defaultdict(list) for h in range(H): for w,a in enumerate(map(int, input().split())): d[a].append((h,w)) res=0 for a,edges in d.items(): if a==0: continue MVC=MinimumVertexCover() dh,dw=dict(),dict() for h,w in edges: if h not in dh: dh[h]=len(dh) if w not in dw: dw[w]=len(dw) MVC.add_edge(dh[h],dw[w]) X,Y=MVC.solve() res+=len(X)+len(Y) print(res)