#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* debug macros */ #ifdef WAFDAYO #define DBG_PRINT(s, t, u) { std::cerr << s << " \e[2m=\e[m \e[1m" << t << "\e[m" << u; } #else #define DBG_PRINT(s, t, u) {} #endif #define dbg(x) DBG_PRINT(#x, x, std::endl) #define dbgc(x) DBG_PRINT(#x, x, ", ") #define idbg(x, i) DBG_PRINT(#x "[" << i << "]", x[i], std::endl) #define idbgc(x, i) DBG_PRINT(#x "[" << i << "]", x[i], ", ") /* IO utilities */ struct read_item { read_item() {}; template operator T() { T t; std::cin >> t; return t; } }; /* types and constants */ typedef long long i64; const i64 inf = (i64)1.05e18; // const int inf = (int)1.05e9; /* Dinic Algorithm for Maximum Flow */ /* generic case: O( E V^2 ) */ /* network with unit capacities: O( min{E V^(2/3), E^(3/2)} ) */ /* network with each vertex (except for s, t) having a single (entering or outgoing) edge of capacity 1: O( E sqrt(V) ) */ struct edge { int to, rev; i64 cap; }; typedef vector vertex; typedef vector graph; void compute_level(int s, vector& level, graph& g) { level.resize(g.size()); fill(level.begin(), level.end(), -1); queue q; level[s] = 0; q.push(s); while(!q.empty()) { const int v = q.front(); q.pop(); for(const auto& e : g[v]) { const int w = e.to; const i64 c = e.cap; if(c <= 0 || level[w] != -1) continue; level[w] = level[v] + 1; q.push(w); } } } i64 compute_flow_path(int v, int t, i64 f, vector& iter, vector& level, graph& g) { if(v == t) return f; for(int& i = iter[v]; i < (int)g[v].size(); ++i) { auto& e = g[v][i]; const i64 c = e.cap; const int w = e.to; if(c <= 0 || level[v] >= level[w]) continue; const i64 d = compute_flow_path(w, t, min(f, c), iter, level, g); if(d <= 0) continue; e.cap -= d; g[w][e.rev].cap += d; return d; } return 0; } i64 max_flow(int s, int t, graph& g) { i64 flow = 0; vector level(g.size()); vector iter(g.size()); while(true) { compute_level(s, level, g); if(level[t] == -1) break; fill(iter.begin(), iter.end(), 0); while(true) { const i64 f = compute_flow_path(s, t, inf, iter, level, g); flow += f; if(f <= 0) break; } } return flow; } void add_edge(graph& g, int from, int to, i64 cap) { g[from].push_back({to, g[to].size(), cap}); g[to].push_back({from, g[from].size() - 1, 0}); } int main() { const int h = read_item(); const int w = read_item(); vector> gs(h); for(auto& v : gs) { v.resize(w); } for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { gs[i][j] = read_item(); } } vector rs(h), cs(w); for(int i = 0; i < h; i++) { rs[i] = read_item(); } for(int i = 0; i < w; i++) { cs[i] = read_item(); } graph g(2 + h * w + w + h); const int left = 2; const int right = 2 + w + h; for(int i = 0; i < w; i++) { add_edge(g, 0, left + i, cs[i]); for(int j = 0; j < h; j++) { add_edge(g, left + i, right + i * h + j, inf); } } for(int i = 0; i < h; i++) { add_edge(g, 0, left + w + i, rs[i]); for(int j = 0; j < w; j++) { add_edge(g, left + w + i, right + j * h + i, inf); } } for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { add_edge(g, right + j * h + i, 1, gs[i][j]); } } i64 f = max_flow(0, 1, g); i64 ans = 0; for(int i = 0; i < h; i++) { ans += rs[i]; } for(int i = 0; i < w; i++) { ans += cs[i]; } ans -= f; printf("%lld\n", ans); return 0; } /* wafdayo~~~ */