// https://cp-algorithms.com/graph/mpm.html
use std::cmp::*;
type FlowType = i64;
struct MPMGraph {
size: usize,
edge: Vec<(usize, usize, FlowType)>,
}
impl MPMGraph {
pub fn new(size: usize) -> Self {
MPMGraph {
size: size,
edge: vec![],
}
}
fn add_edge(&mut self, src: usize, dst: usize, capa: FlowType) {
assert!(src < self.size && dst < self.size);
if src != dst {
self.edge.push((src, dst, capa));
self.edge.push((dst, src, 0));
}
}
fn flow(&mut self, src: usize, dst: usize) -> FlowType {
// 多重辺のマージ
self.edge.sort();
self.edge.dedup_by(|a, b| {
if a.0 == b.0 && a.1 == b.1 {
b.2 += a.2;
true
} else {
false
}
});
// 逆辺への参照を取得
let mut edge = Vec::with_capacity(self.edge.len());
for &(s, t, c) in self.edge.iter() {
let k = self.edge.binary_search_by(|e| (e.0, e.1).cmp(&(t, s))).unwrap();
edge.push((s, t, c, k));
}
// フローが流れなくなるまでループ
let mut ans = 0;
loop {
// 到達可能性を確かめる
let mut graph = vec![vec![]; self.size];
let mut inv_graph = vec![vec![]; self.size];
for &(s, t, c, _) in edge.iter() {
if c > 0 {
graph[s].push(t);
inv_graph[t].push(s);
}
}
let depth = MPMGraph::bfs(src, dst, &graph);
// 到達不能
if depth[dst] >= self.size {
break;
}
let inv_depth = MPMGraph::bfs(dst, src, &inv_graph);
// depth, inv_depthから使用される可能性のある辺のみからなるグラフを構築
// pin, pout は流入、流出
let mut flow_graph = vec![vec![]; self.size];
let mut inv_flow_graph = vec![vec![]; self.size];
let mut pin = vec![0; self.size];
let mut pout = vec![0; self.size];
for (i, &(s, t, c, _)) in edge.iter().enumerate() {
if c > 0 && depth[s] + 1 == depth[t] && inv_depth[t] + 1 == inv_depth[s] {
flow_graph[s].push((t, i));
pout[s] += c;
pin[t] += c;
inv_flow_graph[t].push((s, i));
}
}
// src, dstは適当に初期化
let inf = 1_000_000_000_000_000_000i64;
pout[src] = inf;
pin[src] = inf;
pout[dst] = inf;
pin[dst] = inf;
// 採用されたか
let mut alive = vec![true; self.size];
alive[src] = false;
alive[dst] = false;
// どこまでみたかのアレ
let mut it = vec![0; self.size];
let mut inv_it = vec![0; self.size];
loop {
// ポテンシャルが最小のものを検索
let mut v = (pout[src], src);
for (u, (pin, (pout, alive))) in pin.iter().zip(pout.iter().zip(alive.iter())).enumerate() {
let pot = min(*pin, *pout);
assert!(pot >= 0);
if *alive {
v = min(v, (pot, u));
}
}
// 存在しないならbreak
if v.1 == src {
break;
}
alive[v.1] = false;
if v.0 == 0 {
MPMGraph::remove_node(v.1, &flow_graph, &inv_flow_graph, &mut edge, &mut pin, &mut pout);
continue;
}
ans += v.0;
MPMGraph::push(v.1, dst, v.0, &flow_graph, &mut edge, &mut it, &mut pin, &mut pout);
MPMGraph::push(v.1, src, v.0, &inv_flow_graph, &mut edge, &mut inv_it, &mut pout, &mut pin);
MPMGraph::remove_node(v.1, &flow_graph, &inv_flow_graph, &mut edge, &mut pin, &mut pout);
}
}
ans
}
fn push(src: usize, dst: usize, flow: FlowType, graph: &[Vec<(usize, usize)>], edge: &mut [(usize, usize, FlowType, usize)], it: &mut [usize], pin: &mut [FlowType], pout: &mut [FlowType]) {
let mut q = std::collections::VecDeque::new();
let mut assign = vec![0; graph.len()];
assign[src] = flow;
q.push_back(src);
while let Some(v) = q.pop_front() {
assert!(assign[v] > 0);
assert!(pout[v] >= assign[v]);
if v == dst {
break;
}
let mut f = assign[v];
for &(u, k) in graph[v][it[v]..].iter() {
let capa = min(edge[k].2, min(pout[u], pin[u]));
if capa > 0 && assign[u] == 0 {
q.push_back(u);
}
if capa >= f {
edge[k].2 -= f;
edge[edge[k].3].2 += f;
pout[v] -= f;
pin[u] -= f;
assign[u] += f;
f = 0;
break;
}
edge[k].2 -= capa;
edge[edge[k].3].2 += capa;
pout[v] -= capa;
pin[u] -= capa;
assign[u] += capa;
f -= capa;
it[v] += 1;
}
assert!(f == 0);
}
assert!(assign[dst] == flow);
}
fn remove_node(v: usize, graph: &[Vec<(usize, usize)>], inv_graph: &[Vec<(usize, usize)>], edge: &mut [(usize, usize, FlowType, usize)], pin: &mut [FlowType], pout: &mut [FlowType]) {
for &(u, k) in graph[v].iter() {
let capa = min(edge[k].2, min(pin[u], pout[v]));
pin[u] -= capa;
pout[v] -= capa;
}
for &(u, k) in inv_graph[v].iter() {
let capa = min(edge[k].2, min(pout[u], pin[v]));
pout[u] -= capa;
pin[v] -= capa;
}
}
fn bfs(src: usize, dst: usize, graph: &[Vec]) -> Vec {
let mut depth = vec![graph.len(); graph.len()];
depth[src] = 0;
let mut q = std::collections::VecDeque::new();
q.push_back(src);
'outer: while let Some(v) = q.pop_front() {
for &u in graph[v].iter() {
if depth[u] > depth[v] + 1 {
depth[u] = depth[v] + 1;
if u == dst {
break 'outer;
}
q.push_back(u);
}
}
}
depth
}
}
fn run() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut it = s.trim().split_whitespace();
let h: usize = it.next().unwrap().parse().unwrap();
let w: usize = it.next().unwrap().parse().unwrap();
let a: Vec> = (0..h).map(|_| (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect()).collect();
let r: Vec = (0..h).map(|_| it.next().unwrap().parse().unwrap()).collect();
let c: Vec = (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect();
let mut graph = MPMGraph::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();
}