// https://37zigen.com/fujishige/ pub struct Fujishige { size: usize, graph: Vec>, } impl Fujishige { pub fn new(size: usize) -> Self { Self { size: size, graph: vec![vec![]; size], } } pub fn add_edge(&mut self, src: usize, dst: usize, capa: i64) { assert!(src != dst); assert!(src < self.size && dst < self.size); let x = self.graph[src].len(); let y = self.graph[dst].len(); self.graph[src].push((dst, capa, y)); self.graph[dst].push((src, 0, x)); } pub fn flow(&mut self, src: usize, dst: usize) -> i64 { assert!(src != dst); assert!(src < self.size && dst < self.size); let size = self.size; let mut pass = vec![0i64; size]; let mut sum = vec![0; size]; let mut topo = Vec::with_capacity(size); let mut used = vec![false; size]; let mut f = 1 << 29; while f > 0 { loop { sum.iter_mut().for_each(|s| *s = 0); topo.clear(); topo.push(src); used.iter_mut().for_each(|u| *u = false); used[src] = true; for i in 0.. { if used[dst] || i >= topo.len() { break; } let v = topo[i]; for &(u, c, _) in self.graph[v].iter() { sum[u] += c; if !used[u] && sum[u] >= f { used[u] = true; topo.push(u); } } } if !used[dst] { break; } pass[dst] = f; for v in topo.drain(..).rev() { let mut pos = 0; while let Some(&(u, capa, inv)) = self.graph[v].get(pos) { if u != src && pass[u] > 0 && capa > 0 { let c = capa.min(pass[u]); pass[u] -= c; pass[v] += c; self.graph[v][pos].1 -= c; self.graph[u][inv].1 += c; } pos += 1; } } } f /= 2; } pass[src] } } fn read() -> (usize, usize, Vec>, Vec, Vec) { let mut s = String::new(); use std::io::*; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let mut next = || it.next().unwrap().parse::().unwrap(); let h = next() as usize; let w = next() as usize; let mut g = vec![vec![0i64; w]; h]; let mut r = vec![0; h]; let mut c = vec![0; w]; for g in g.iter_mut().flatten().chain(&mut r).chain(&mut c) { *g = next(); } (h, w, g, r, c) } fn run() { let (h, w, a, r, c) = read(); let mut graph = Fujishige::new(h + w + 2); let src = h + w; let dst = src + 1; for (i, a) in a.iter().enumerate() { let mut local = 0; for (j, a) in a.iter().enumerate() { graph.add_edge(h + j, i, *a); local += *a; } graph.add_edge(i, dst, local); } let mut sum = 0; for (i, r) in r.iter().enumerate() { sum += *r; graph.add_edge(src, i, *r); } for (i, c) in c.iter().enumerate() { sum += *c; graph.add_edge(src, i + h, *c); } let ans = sum - graph.flow(src, dst); println!("{}", ans); } fn main() { run(); }