import sys from collections import defaultdict, deque def main(): input = sys.stdin.read().split() idx = 0 H = int(input[idx]); idx +=1 W = int(input[idx]); idx +=1 matrix = [] elements = defaultdict(list) for i in range(H): row = list(map(int, input[idx:idx+W])) idx += W matrix.append(row) for j in range(W): v = row[j] if v != 0: elements[v].append((i, j)) sorted_values = sorted(elements.keys(), reverse=True) total_ops = 0 for v in sorted_values: nodes = elements[v] rows = set() cols = set() edges = defaultdict(list) for (i, j) in nodes: rows.add(i) cols.add(j) edges[i].append(j) graph = {} for u in rows: graph[u] = edges[u] match_U = {} match_V = {} dist = {} def bfs(): queue = deque() for u in graph: if u not in match_U: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist[None] = float('inf') while queue: u = queue.popleft() if u is not None: for v in graph.get(u, []): if dist.get(match_V.get(v), float('inf')) == float('inf'): dist[match_V.get(v)] = dist[u] + 1 queue.append(match_V.get(v)) return dist[None] != float('inf') def dfs(u): if u is not None: for v in graph.get(u, []): if dist.get(match_V.get(v), float('inf')) == dist[u] + 1: if dfs(match_V.get(v)): match_U[u] = v match_V[v] = u return True dist[u] = float('inf') return False return True result = 0 while bfs(): for u in graph: if u not in match_U: if dfs(u): result +=1 total_ops += result print(total_ops) if __name__ == "__main__": main()