#include int ri() { int n; scanf("%d", &n); return n; } /* copied from https://gist.github.com/MiSawa/9759784 */ /* edited by QCFium */ struct Dinic { private: typedef int64_t Cap; static const Cap INF = 1000000000000000000; struct LCNode { typedef LCNode *Ptr; Ptr ch[2], par, min_node; Cap val, min_val, lazy; int name; LCNode() : par(0), min_node(this), val(INF), min_val(INF), lazy(0) { ch[0] = ch[1] = 0; } inline void push() { if (lazy == 0) return; val += lazy; min_val += lazy; for (int i = 0; i < 2; i++) if (ch[i]) ch[i]->lazy += lazy; lazy = 0; } inline void update() { push(); if (ch[0]) { min_val = ch[0]->min_val + ch[0]->lazy; min_node = ch[0]->min_node; } if (!ch[0] || min_val > val) { min_val = val; min_node = this; } if (ch[1] && min_val > ch[1]->min_val + ch[1]->lazy) { min_val = ch[1]->min_val + ch[1]->lazy; min_node = ch[1]->min_node; } } inline void set_value(Cap v) { expose(); val = v; update(); } inline Cap get_value() { expose(); return val; } inline Ptr get_min_node_on_path() { expose(); return min_node; } inline void add_to_path(Cap c) { expose(); lazy += c; push(); } inline int state() { if(par && par->ch[0] == this) return -1; if(par && par->ch[1] == this) return +1; return 0; } inline void rotate() { Ptr p = par; p->push(); push(); bool lr = state()+1; if (p->state()) p->par->ch[p->state()>0] = this; par = p->par; p->ch[lr] = ch[!lr]; if (ch[!lr]) ch[!lr]->par = p; (p->par = this)->ch[!lr] = p; p->update(); update(); } inline void splay() { while (state()) { int s = state() * par->state(); if (s) (s == 1 ? par : this)->rotate(); rotate(); } push(); } inline void expose() { if (!par) return; for (Ptr p = this; p; p = p->par) p->splay(); for (Ptr p = this; p->par; p = p->par) p->par->ch[1] = p; splay(); } inline void cut() { expose(); if (!ch[0]) return; ch[0]->par = 0; ch[0]->push(); ch[0] = 0; update(); } inline void link_to(Ptr p) { expose(); par = p; } inline Ptr find_root() { expose(); Ptr p = this; while (p->ch[0]) p = p->ch[0]; p->expose(); return p; } }; struct E{ int dst; Cap cap; int rev; E(int dst, Cap cap, int rev) : dst(dst), cap(cap), rev(rev) {} }; int n; std::vector > g; std::vector level, active; std::vector lc; inline void unuse_edge(E &e) { E &ee = g[e.dst][e.rev]; int u = ee.dst; Cap use = ee.cap - lc[u].get_value(); e.cap += use; ee.cap -= use; active[u] = false; lc[u].cut(); lc[u].set_value(INF); } inline void init(){ lc.resize(n); active.assign(n, false); for (int i = 0; i < n; i++) lc[i].name = i; } Cap dfs(const int &s, const int &t) { std::vector iter(n); for (int i = 0; i < n; i++) iter[i] = (int) (g[i].size()) - 1; Cap res = 0; while(1){ const int &u = lc[t].find_root()->name; if (u == s) { Cap f = lc[t].get_min_node_on_path()->get_value(); res += f; lc[t].add_to_path(-f); while (1) { int v = lc[t].get_min_node_on_path()->name; Cap f = lc[v].get_value(); if (f > 0) break; unuse_edge(g[v][iter[v]]); } } else { for (int &i = iter[u]; i >= 0; --i) { E &e = g[u][i], &ee = g[e.dst][e.rev]; int v = e.dst; if (level[u]-1 != level[v] || ee.cap <= 0) continue; active[u] = true; lc[u].set_value(ee.cap); lc[u].link_to(&lc[v]); break; } if (active[u]) continue; if (u == t) break; level[u] = -1; for (auto& e : g[u]) if (active[e.dst] && iter[e.dst] == e.rev) unuse_edge(g[e.dst][e.rev]); } } for (int i = 0; i < n; i++) if (active[i]) unuse_edge(g[i][iter[i]]); return res; } public: Dinic(int n) : n(n), g(n) {} inline void add_hen(int src, int dst, Cap cap, bool direct) { if (src == dst) return; g[src].push_back(E(dst,cap,g[dst].size())); g[dst].push_back(E(src,direct?0:cap ,g[src].size() - 1)); } Cap run(int s, int t) { // O(NMlogN) init(); std::vector q(n); for (Cap flow = 0; ;) { level.assign(n, -1); int ql = 0, qr = 0; level[q[qr++] = s] = 0; while (ql != qr && level[t] == -1) { int u = q[ql++]; for (auto& e : g[u]) if (e.cap > 0 && level[e.dst] == -1) level[ q[qr++] = e.dst ] = level[u] + 1; } if (level[t] == -1) return flow; flow += dfs(s, t); } } }; int main() { int h = ri(); int w = ri(); int a[h][w]; for (auto &i : a) for (auto &j : i) j = ri(); int b[h]; for (auto &i : b) i = ri(); int c[w]; for (auto &i : c) i = ri(); Dinic dinic(h + w + h * w + 2); int goal = h + w + h * w + 1; int64_t base = 0; for (int i = 0; i < h; i++) { int64_t cost = std::accumulate(a[i], a[i] + w, 0LL) - b[i]; if (cost < 0) base += cost; dinic.add_hen(0, i + 1, std::max(0, cost), true); dinic.add_hen(i + 1, goal, std::max(0, -cost), true); } for (int i = 0; i < w; i++) { int64_t cost = -c[i]; for (int j = 0; j < h; j++) cost += a[j][i]; dinic.add_hen(0, h + 1 + i, std::max(0, cost), true); dinic.add_hen(h + 1 + i, goal, std::max(0, -cost), true); } for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { base += -a[i][j]; dinic.add_hen(i + 1, h + w + i * w + j + 1, 10000000000000000, true); dinic.add_hen(h + j + 1, h + w + i * w + j + 1, 10000000000000000, true); dinic.add_hen(h + w + i * w + j + 1, goal, a[i][j], true); } std::cout << std::max(0, -(base + dinic.run(0, goal))) << std::endl; return 0; }