#include #include #include #include #include #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,ssse3,sse4a") using namespace std; class Stack { private: const int N, H; vector node; public: Stack(const int _N, const int _H) : N(_N), H(_H), node(N+H){ clear(); } bool empty(const int h) const { return node[N+h] == N+h; } int top(const int h) const { return node[N+h]; } void pop(const int h){ node[N+h] = node[node[N+h]]; } void push(const int h, const int u){ node[u] = node[N+h], node[N+h] = u; } void clear(){ iota(node.begin() + N, node.end(), N); } }; // class Queue { // private: // const int N, H; // vector node, last; // public: // Queue(const int _N, const int _H) : N(_N), H(_H), node(N+H), last(H){ clear(); } // bool empty(const int h) const { return node[N+h] == N+h; } // int top(const int h) const { return node[N+h]; } // void pop(const int h){ node[N+h] = node[node[N+h]]; if(empty(h)) last[h] = N+h; } // void push(const int h, const int u){ node[node[last[h]] = u] = N+h, last[h] = u; } // void clear(){ iota(node.begin() + N, node.end(), N); iota(last.begin(), last.end(), N); } // }; class List { public: struct node { int prev, next; }; const int N, H; vector dat; List(const int _N, const int _H) : N(_N), H(_H), dat(N+H){ clear(); } bool empty(const int h) const { return (dat[N+h].next == N+h); } bool more_one(const int h) const { return dat[N+h].prev != dat[N+h].next; } void insert(const int h, const int u){ dat[u].prev = dat[N+h].prev, dat[u].next = N+h; dat[dat[N+h].prev].next = u, dat[N+h].prev = u; } void erase(const int u){ dat[dat[u].prev].next = dat[u].next, dat[dat[u].next].prev = dat[u].prev; } void clear(){ for(int i = N; i < N+H; ++i) dat[i].prev = dat[i].next = i; } }; template class PushRelabel { public: struct edge { const int to, rev; T cap; edge(const int _to, const int _rev, const T _cap) : to(_to), rev(_rev), cap(_cap){} }; private: const int V; int s, t, pot_max, checker; vector excess; vector potential, cur_edge, que; List all_ver; Stack act_ver; // Queue act_ver; int calc_active(){ pot_max = -1; for(int i = 0; i < V; ++i){ if(potential[i] < V){ cur_edge[i] = 0; pot_max = max(potential[i], pot_max); all_ver.insert(potential[i], i); if(excess[i] > 0 && i != t) act_ver.push(potential[i], i); }else{ potential[i] = V+1; } } return pot_max; } void bfs(){ for(int i = 0; i < V; ++i) potential[i] = max(potential[i], V); potential[t] = 0; int qh = 0, qt = 0; for(que[qt++] = t; qh++ < qt;){ int u = que[qh-1]; for(const edge& e : G[u]){ if(potential[e.to] == V && G[e.to][e.rev].cap > 0){ potential[e.to] = potential[u] + 1, que[qt++] = e.to; } } } } int init(){ potential[s] = V + 1; bfs(); for(edge& e : G[s]){ if(potential[e.to] < V){ G[e.to][e.rev].cap = e.cap, excess[s] -= e.cap, excess[e.to] += e.cap; e.cap = 0; } } return calc_active(); } int global_relabel(){ bfs(); all_ver.clear(), act_ver.clear(); return calc_active(); } void gap_relabel(const int u){ for(int i = potential[u]; i <= pot_max; ++i){ for(int id = all_ver.dat[V+i].next; id < V; id = all_ver.dat[id].next){ potential[id] = V + 1; } all_ver.dat[V+i].prev = all_ver.dat[V+i].next = V+i; } } int discharge(const int u){ for(int& i = cur_edge[u]; i < (int)G[u].size(); ++i){ edge& e = G[u][i]; if(potential[u] == potential[e.to] + 1 && e.cap > 0){ if(push(u, e)) return potential[u]; } } return relabel(u); } bool push(const int u, edge& e){ const T f = min(e.cap, excess[u]); const int v = e.to; e.cap -= f, excess[u] -= f; G[v][e.rev].cap += f, excess[v] += f; if(excess[v] == f && v != t) act_ver.push(potential[v], v); return (excess[u] == 0); } int relabel(const int u){ ++checker; int prv = potential[u], cur = V; for(int i = 0; i < (int)G[u].size(); ++i){ const edge& e = G[u][i]; if(cur > potential[e.to] + 1 && e.cap > 0){ cur_edge[u] = i; cur = potential[e.to] + 1; } } if(all_ver.more_one(prv)){ all_ver.erase(u); if((potential[u] = cur) == V) return potential[u] = V+1, prv; act_ver.push(cur, u); all_ver.insert(cur, u); pot_max = max(pot_max, cur); }else{ gap_relabel(u); return pot_max = prv - 1; } return cur; } int validate_discharge(const int u){ for(int& i = cur_edge[u]; i < (int)G[u].size(); ++i){ edge& e = G[u][i]; if(potential[u] == potential[e.to] + 1 && e.cap > 0){ if(validate_push(u, e)) return potential[u] - V; } } return validate_relabel(u); } bool validate_push(const int u, edge& e){ T f = min(e.cap, excess[u]); const int v = e.to; e.cap -= f, excess[u] -= f; G[v][e.rev].cap += f, excess[v] += f; if(excess[v] == f) act_ver.push(potential[v] - V, v); return (excess[u] == 0); } int validate_relabel(const int u){ int cur = 2 * V; for(int i = 0; i < (int)G[u].size(); ++i){ const edge& e = G[u][i]; if(cur > potential[e.to] + 1 && e.cap > 0){ cur_edge[u] = i; cur = potential[e.to] + 1; } } potential[u] = cur; act_ver.push(cur - V, u); return cur - V; } void validate(){ for(int i = 0; i < V; ++i){ if(potential[i] >= V){ cur_edge[i] = 0, potential[i] = V + 1; if(excess[i] > 0) act_ver.push(1, i); } } potential[s] = V; int level = 0; while(level >= 0){ if(act_ver.empty(level)){ --level; continue; } int u = act_ver.top(level); act_ver.pop(level); level = validate_discharge(u); } } public: vector > G; PushRelabel(const int node_size) : V(node_size), pot_max(-1), checker(0), excess(V, (T)0), potential(V, 0), cur_edge(V), que(V), all_ver(V, V), act_ver(V, V), G(V){} void add_edge(const int _from, const int _to, const T _cap){ G[_from].emplace_back(_to, (int)G[_to].size(), _cap); G[_to].emplace_back(_from, (int)G[_from].size() - 1, 0); } T solve(const int source, const int sink){ s = source, t = sink; int level = init(); while(level >= 0){ if(act_ver.empty(level)){ --level; continue; } int u = act_ver.top(level); act_ver.pop(level); level = discharge(u); if(checker >= 4 * V){ level = global_relabel(); checker = 0; } } // validate(); return excess[t]; } }; #define getchar getchar_unlocked #define putchar putchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } inline void out(long long n) { short res[20], i = 0; do { res[i++] = n % 10, n /= 10; } while (n); while (i) putchar(res[--i] + '0'); putchar('\n'); } const int MAX_N = 300; int g[MAX_N][MAX_N], r[MAX_N], c[MAX_N]; int main() { int h = in(), w = in(), r, c; PushRelabel pr(h + w + 2); const int s = h + w, t = h + w + 1; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) g[i][j] = in(); long long x, y = 0; for(int i = 0; i < h; ++i){ r = in(), x = accumulate(g[i], g[i] + w, 0LL); if(r >= x) y += r - x; else pr.add_edge(s, i, x - r); } for(int j = 0; j < w; ++j){ c = in(), pr.add_edge(h + j, t, c), y += c; } for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) pr.add_edge(i, j + h, g[i][j]); out(y - pr.solve(s, t)); return 0; }