#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct Graph { struct edge { int rev,from,to; long cap; edge(int r,int f,int t,long c) : rev(r),from(f),to(t),cap(c) {} }; vector> list; Graph(int n = 0) : list(n) {} size_t size() {return list.size();} vector &operator[](int i) {return list[i];} edge &redge(const edge &e) {return list[e.to][e.rev];} void run_flow(edge &e,long f) { assert(f <= e.cap); e.cap -= f; redge(e).cap += f; } void add_edge(int from,int to,long cap) { int fromrev = (int)list[from].size(); int torev = (int)list[to].size(); list[from].push_back(edge(torev,from,to,cap)); list[to].push_back(edge(fromrev,to,from,0)); } }; templatestruct Dinic { T INF; vector level,iter; Dinic(T INF) : INF(INF) {} void bfs(Graph G,int s) { level.assign((int)G.size(),-1); level[s] = 0; queue Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i = 0;i < (int)G[u].size();i++) { auto &e = G[u][i]; if(e.cap && level[e.to] < 0) { level[e.to] = level[u] + 1; Q.push(e.to); } } } } T dfs(Graph &G,int u,int target,T f) { if(u == target) return f; for(int &i = iter[u];i < (int)G[u].size();i++) { auto &e = G[u][i]; if(!e.cap) continue; if(level[u] >= level[e.to]) continue; T flow = dfs(G,e.to,target,min(f,T(e.cap))); if(!flow) continue; G.run_flow(e,flow); return flow; } return 0; } T maxflow(Graph &G,int s,int t) { T flow = 0; while(true) { bfs(G,s); if(level[t] < 0) return flow; iter.assign((int)G.size(),0); while(true) { T f = dfs(G,s,t,INF); if(!f) break; flow += f; } } } vector mincut(Graph G,int s) { vector res((int)G.size()); queue Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); res[u] = true; for(auto e:G[u]) if(e.cap && !res[e.to]) res[e.to] = true,Q.push(e.to); } return res; } }; int H,W,g[300][300],R[300],C[300]; void solve() { cin >> H >> W; long long ans = 0; for(int i = 0;i < H;i++)for(int j = 0;j < W;j++) cin >> g[i][j],ans += g[i][j]; for(int i = 0;i < H;i++) cin >> R[i],ans += R[i]; for(int j = 0;j < W;j++) cin >> C[j],ans += C[j]; Graph G(H*W+H+W+2); int S = H*W+H+W,T = S+1; const long long inf = (long long)1e18; for(int i = 0;i < H;i++)for(int j = 0;j < W;j++) { G.add_edge(S,W*i+j,g[i][j]); G.add_edge(W*i+j,H*W+i,inf); G.add_edge(W*i+j,H*W+H+j,inf); } for(int i = 0;i < H;i++) { long long cost = 0; for(int j = 0;j < W;j++) cost += g[i][j]; G.add_edge(S,H*W+i,R[i]); G.add_edge(H*W+i,T,cost); } for(int j = 0;j < W;j++) { long long cost = 0; for(int i = 0;i < H;i++) cost += g[i][j]; G.add_edge(S,H*W+H+j,C[j]); G.add_edge(H*W+H+j,T,cost); } Dinic dc(inf); long long mf = dc.maxflow(G,S,T); ans -= mf; cout << ans << endl; /* Graph G(H*W+H+W+2); */ /* int S = H*W+H+W,T = S+1; */ /* for(int i = 0;i < H;i++)for(int j = 0;j < W;j++) */ /* { */ /* int g; */ /* cin >> g; */ /* G.add_edge(W*i+j,T,g); */ /* } */ /* long long ans = 0; */ /* const long long inf = (long long)1e18; */ /* for(int i = 0;i < H;i++) */ /* { */ /* int R; */ /* cin >> R; */ /* ans += R; */ /* G.add_edge(S,H*W+i,R); */ /* for(int j = 0;j < W;j++) G.add_edge(H*W+i,W*i+j,inf); */ /* } */ /* for(int j = 0;j < W;j++) */ /* { */ /* int C; */ /* cin >> C; */ /* ans += C; */ /* G.add_edge(S,H*W+H+j,C); */ /* for(int i = 0;i < H;i++) G.add_edge(H*W+H+j,W*i+j,inf); */ /* } */ /* Dinic dc(inf); */ /* long long mf = dc.maxflow(G,S,T); */ /* ans -= mf; */ /* cout << ans << endl; */ } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) solve(); }