#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx") #include using namespace std; #include #include #include #include struct residual_graph { using cap_type = long long; struct edge { int to; cap_type cap; int rev; edge(int t = 0, cap_type c = 0, int r = 0): to(t), cap(c), rev(r) {} }; int N; std::vector iter; std::vector> pool; std::vector edges; residual_graph(int N): N(N), iter(N + 1) {} void add_edge(int from, int to, cap_type cap, cap_type rev_cap) { iter[from]++; iter[to]++; pool.emplace_back(from, to, cap); } void build() { for(int i = 0; i < N; i++) { iter[i + 1] += iter[i]; } edges.resize(pool.size() * 2); for(auto&& p: pool) { int fi = --iter[std::get<0>(p)]; int ti = --iter[std::get<1>(p)]; edges[fi] = edge(std::get<1>(p), std::get<2>(p), ti); edges[ti] = edge(std::get<0>(p), 0, fi); } } inline edge& operator[](int i) { return edges[i]; } }; struct goldberg_tarjan { using cap_type = long long; struct edge { int to; cap_type cap; edge(int t, cap_type c, int r): to(t), cap(c) {} }; int N; residual_graph G; std::vector exc; std::vector h; std::vector> que; std::vector qi; std::vector ei; std::bitset<2048> inque; const cap_type INF = 1e18; goldberg_tarjan(int n): N(n), G(n) {} void add_edge(int from, int to, cap_type cap, cap_type rev_cap = 0) { G.add_edge(from, to, cap, rev_cap); } void build() { G.build(); } void push(int from, int ei) { cap_type fl = std::min(exc[from], G[ei].cap); G[ei].cap -= fl; G[G[ei].rev].cap += fl; exc[from] -= fl; exc[G[ei].to] += fl; } void relabel(int v) { h[v] = N; for(int i = G.iter[v]; i < G.iter[v + 1]; i++) { auto& e = G[i]; if(e.cap > 0 && h[v] > h[e.to] + 1) { ei[v] = i; h[v] = h[e.to] + 1; } } } int global_relabeling(int t) { std::fill(std::begin(h), std::end(h), N); for(int i = 0;i < N;i++) { que[i].clear(); } inque.reset(); int i = 0, qr = 0; std::vector& Q = qi; Q[qr++] = t; h[t] = 0; int hi = 0; while(i < qr) { int v = Q[i++]; hi = h[v]; if(exc[v] > 0 && v != t) { que[h[v]].emplace_back(v); inque.set(v); } for(int gi = G.iter[v]; gi < G.iter[v + 1]; gi++) { auto& e = G[gi]; if(G[e.rev].cap > 0 && h[v] + 1 < h[e.to]) { h[e.to] = h[v] + 1; Q[qr++] = e.to; } } } std::copy(std::begin(G.iter), std::begin(G.iter) + N, std::begin(ei)); std::fill(std::begin(qi), std::end(qi), 0); return hi; } void gap_relabeling(int g) { for(int v = 0; v < N; v++) { if(h[v] > g) { h[v] = N; } } } cap_type max_flow(int s, int t) { exc.assign(N, 0); exc[s] = INF; h.assign(N, 0); int cnt = 0; que.resize(N); qi.assign(N, 0); ei.resize(N); global_relabeling(t); if(h[s] == N) return 0; for(int di = h[s]; di >= 0;) { if(qi[di] == que[di].size()) { di--; continue; } int v = que[di][qi[di]++]; inque.reset(v); if(exc[v] == 0 || v == t) continue; for(int& i = ei[v]; i < G.iter[v + 1]; i++) { auto& e = G[i]; if(e.cap > 0 && h[v] == h[e.to] + 1) { push(v, i); if(exc[e.to] > 0 && e.to != t && !inque.test(e.to)) { que[h[e.to]].emplace_back(e.to); inque.set(e.to); } if(exc[v] == 0) break; } } if(exc[v] == 0) continue; relabel(v); if(h[v] < N) { di = h[v]; que[h[v]].emplace_back(v); inque.set(v); } if(qi[di] == que[di].size()) { gap_relabeling(di); di--; } if(++cnt % (N * 4) == 0) { di = global_relabeling(t); } } return exc[t]; } }; #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() template static inline std::vector ndvec(size_t&& n, T val) noexcept { return std::vector(n, std::forward(val)); } template static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept { return std::vector(tail)...))>(n, ndvec(std::forward(tail)...)); } template struct chain { Cond cond; chain(Cond cond) : cond(cond) {} bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; } }; template chain make_chain(Cond cond) { return chain(cond); } int main() { cin.tie(nullptr); std::ios::sync_with_stdio(false); int H, W; cin >> H >> W; goldberg_tarjan gt(H + W + 2); int s = H + W; int t = s + 1; vector A(H, 0); rep(i,0,H) rep(j,0,W) { i64 g; cin >> g; A[i] += g; gt.add_edge(i, H + j, g); } i64 sum = 0; rep(i,0,H) { i64 r; cin >> r; i64 MIN = std::min(A[i], r); sum += r - MIN; gt.add_edge(s, i, A[i] - MIN); } rep(i,0,W) { i64 r; cin >> r; sum += r; gt.add_edge(H + i, t, r); } cout << sum - gt.max_flow(s, t) << "\n"; }