#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct PrimalDual{ struct edge{ int to; TF cap; TC cost; int rev; edge(){} edge(int to,TF cap,TC cost,int rev): to(to),cap(cap),cost(cost),rev(rev){} }; static const TC INF; vector> G; vector h,dist; vector prevv,preve; PrimalDual(){} PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){} void add_edge(int u,int v,TF cap,TC cost){ G[u].emplace_back(v,cap,cost,G[v].size()); G[v].emplace_back(u,0,-cost,G[u].size()-1); } void dijkstra(int s){ struct P{ TC first; int second; P(TC first,int second):first(first),second(second){} bool operator<(const P&a) const{return a.first que; fill(dist.begin(),dist.end(),INF); dist[s]=0; que.emplace(dist[s],s); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(dist[v]0){ dijkstra(s); if(dist[t]==INF){ ok=0; return res; } for(int v=0;v<(int)h.size();v++) if(dist[v] const TC PrimalDual::INF = numeric_limits::max()/2; template struct NegativeEdge{ PrimalDual G; vector fs; TC sum; int S,T; NegativeEdge(){} NegativeEdge(int n):G(n+2),fs(n+2,0),sum(0),S(n),T(n+1){} void use_edge(int u,int v,TF cap,TC cost){ fs[u]-=cap; fs[v]+=cap; sum=sum+cost*cap; } void add_edge(int u,int v,TF cap,TC cost){ if(cost0){ f+=fs[i]; G.add_edge(S,i,+fs[i],TC(0)); } if(fs[i]<0){ G.add_edge(i,T,-fs[i],TC(0)); } } return sum+G.flow(S,T,f,ok); } TC flow(int ts,int tt,TF tf,int &ok){ fs[ts]+=tf; fs[tt]-=tf; return flow(ok); } }; //INSERT ABOVE HERE signed main(){ int h,w; cin>>h>>w; vector< vector > G(h,vector(w)); for(int i=0;i>G[i][j]; vector rs(h),cs(w); for(int i=0;i>rs[i]; for(int j=0;j>cs[j]; using ll = long long; NegativeEdge F(h+w+3); int S=h+w; int T=S+1; int Z=T+1; ll sr=0,sc=0; for(int i=0;isc) F.add_edge(Z,T,sr-sc,0); cout<