// 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));
}
}
#[inline(never)]
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 deg = vec![0; self.size];
for e in self.edge.iter() {
deg[e.0] += 1;
}
let mut graph = Vec::with_capacity(self.size);
for deg in deg.into_iter() {
graph.push(Vec::with_capacity(deg));
}
// グラフの構築
let mut used = vec![false; self.edge.len()];
for (i, &(s, t, c)) in self.edge.iter().enumerate() {
if used[i] {
continue;
}
let x = graph[s].len();
let y = graph[t].len();
let k = self.edge.binary_search_by(|e| (e.0, e.1).cmp(&(t, s))).unwrap();
graph[s].push((t, c, y));
graph[t].push((s, self.edge[k].2, x));
used[i] = true;
used[k] = true;
}
// フローが流れなくなるまでループ
let mut it = vec![0; self.size];
let mut ans = 0;
loop {
// 到達可能性を確かめる
let depth = MPMGraph::bfs(src, dst, &graph);
// 到達不能
if depth[dst] >= self.size {
break;
}
it.clear();
it.resize(self.size, 0);
loop {
let f = MPMGraph::dfs(dst, src, &mut graph, &mut it, 1_000_000_000_000_000_000i64, &depth);
if f == 0 {
break;
}
ans += f;
}
}
ans
}
#[inline(never)]
fn dfs(v: usize, src: usize, graph: &mut [Vec<(usize, FlowType, usize)>], it: &mut [usize], mut capa: FlowType, depth: &[usize]) -> FlowType {
if v == src {
return capa;
}
let mut sum = 0;
for i in it[v]..graph[v].len() {
let (u, _, inv) = graph[v][i];
if depth[u] < depth[v] && graph[u][inv].1 > 0 {
let c = min(graph[u][inv].1, capa);
let f = MPMGraph::dfs(u, src, graph, it, c, depth);
sum += f;
capa -= f;
graph[v][i].1 += f;
graph[u][inv].1 -= f;
if capa == 0 {
return sum;
}
}
it[v] += 1;
}
sum
}
#[inline(never)]
fn bfs(src: usize, dst: usize, graph: &[Vec<(usize, FlowType, usize)>]) -> 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, c, _) in graph[v].iter() {
if c > 0 && 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();
}