#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::(); let (h, w) = (v[0], v[1]); let mut poses = HashMap::new(); for y in 0..h { let row = read_vec::(); for x in 0..w { if row[x] == 0 { continue; } poses.entry(row[x]).or_insert(vec![]).push((x, y)); } } let mut ans = 0; for ref v in poses.values() { let s = h + w; let t = h + w + 1; let mut flow = Solver::new(h + w + 2); for y in 0..h { flow.add_edge(s, y, 1); } for x in 0..w { flow.add_edge(h + x, t, 1); } for &(x, y) in *v { flow.add_edge(y, h + x, 1); } let m = flow.max_flow(s, t); // debug!(m, v); ans += m; } println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone, Copy)] struct Edge { to: usize, cap: i64, rev: usize, } #[derive(Clone)] struct Solver { edges: Vec>, used: Vec, } impl Solver { fn new(v: usize) -> Solver { Solver { edges: vec![Vec::new(); v], used: vec![false; v], } } fn add_edge(&mut self, from: usize, to: usize, cap: i64) { let rev = self.edges[to].len(); self.edges[from].push(Edge { to: to, cap: cap, rev: rev, }); let rev = self.edges[from].len() - 1; self.edges[to].push(Edge { to: from, cap: 0, rev: rev, }); } fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 { if v == t { return f; } self.used[v] = true; for i in 0..self.edges[v].len() { let edge = self.edges[v][i]; if !self.used[edge.to] && edge.cap > 0 { let d = self.dfs(edge.to, t, std::cmp::min(f, edge.cap)); if d > 0 { self.edges[v][i].cap -= d; self.edges[edge.to][edge.rev].cap += d; return d; } } } 0 } fn max_flow(&mut self, s: usize, t: usize) -> i64 { let mut flow = 0; loop { self.used = vec![false; self.edges.len()]; let f = self.dfs(s, t, std::i64::MAX); if f == 0 { return flow; } flow += f; } } }