// 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 f = 2i64.pow(29); let mut sum = vec![0; size]; let mut topo = Vec::with_capacity(size); let mut used = vec![false; size]; let mut pass = vec![0i64; size]; while f > 0 { used.iter_mut().for_each(|u| *u = false); used[src] = true; topo.clear(); topo.push(src); sum.iter_mut().for_each(|s| *s = 0); loop { 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(1..).rev() { sum[v] = 0; used[v] = false; let mut c = pass[v]; pass[v] = 0; let mut pos = 0; while let Some(&(u, _, inv)) = self.graph[v].get(pos) { sum[u] = 0; if used[u] { let capa = self.graph[u][inv].1.min(c); c -= capa; pass[u] += capa; self.graph[u][inv].1 -= capa; self.graph[v][pos].1 += capa; } 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(); }