#ifdef MAIN ================================================================================================================================ +library{ name:dinic_notmine } int solve(){ lin(h, w); vector> g(h, vector(w)); rep(h)in(g[i]); vin(lint, r, h); vin(lint, c, w); each(r)e *= 2; each(c)e *= 2; Dinic d(h+w+2); rep(h)rep(j, w){ d.add_edge(0, 1+i, g[i][j]); d.add_edge(0, 1+h+j, g[i][j]); d.add_edge(1+i, 1+h+j, g[i][j]); d.add_edge(1+h+j, 1+i, g[i][j]); } rep(h)d.add_edge(1+i, 1+h+w, r[i]); rep(j, w)d.add_edge(1+h+j, 1+h+w, c[j]); lint ans = 0; each(r)ans += e; each(c)ans += e; ans -= d.max_flow(0, 1+h+w); out(ans/2); return 0; } #endif MAIN ================================================================================================================================ //sub-BOF // desktop // author: Tqk // #define _AOJ_ #define _C_INPUT_ // #pragma region template // #pragma region basic #define IN_FILE "./in.txt" //#pragma GCC optimize ("O3") #pragma warning(disable: 4455 4244 4067 4068 4996) #pragma GCC target ("avx") #pragma GCC diagnostic ignored "-Wliteral-suffix" #define NOMINMAX #ifdef _ENV_TQK_ #include #endif #include "bits/stdc++.h" using namespace std; typedef int64_t lint; typedef long double ld; typedef string cs; #define linf 1152921504606846976 #ifndef _AOJ_ inline lint operator""z(const unsigned long long n){ return lint(n); } #endif templateinline T operator-(const vector& a,const size_t&i){return a.at(i);} // #pragma endregion // #pragma region rep #define _vcppunko3(tuple) _getname3 tuple #define _vcppunko4(tuple) _getname4 tuple #define _getname4(_1,_2,_3,_4,name,...) name #define _getname3(_1,_2,_3,name,...) name #define _trep2(tuple) _rep2 tuple #define _trep3(tuple) _rep3 tuple #define _trep4(tuple) _rep4 tuple #define _rep1(n) for(lint i=0;i=0;--i) #define _per2(i,n) for(lint i=n-1;i>=0;--i) #define _per3(i,a,b) for(lint i=b-1;i>=a;--i) #define _per4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c) #define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__)) #define per(...) _vcppunko4((__VA_ARGS__,_tper4,_tper3,_tper2,_per1))((__VA_ARGS__)) #define _tall2(tuple) _all2 tuple #define _tall3(tuple) _all3 tuple #define _all1(v) v.begin(),v.end() #define _all2(v,a) v.begin(),v.begin()+a #define _all3(v,a,b) v.begin()+a,v.begin+b #define all(...) _vcppunko3((__VA_ARGS__,_tall3,_tall2,_all1))((__VA_ARGS__)) #define each(c) for(auto &e:c) // #pragma endregion // #pragma region io template istream& operator>>(istream& is,vector& vec); template istream& operator>>(istream& is,array& vec); template istream& operator>>(istream& is,pair& p); template ostream& operator<<(ostream& os,vector& vec); template ostream& operator<<(ostream& os,pair& p); template istream& operator>>(istream& is,vector& vec){ for(T& x: vec) is>>x;return is; } template istream& operator>>(istream& is,pair& p){ is>>p.first;is>>p.second;return is; } template ostream& operator<<(ostream& os,pair& p){ os< ostream& operator<<(ostream& os,vector& vec){ if(vec.size())os< ostream& operator<<(ostream& os,deque& deq){ if(deq.size())os< ostream& operator<<(ostream& os,set& s){ each(s)os< ifstream& operator>>(ifstream& is,vector& vec); template ifstream& operator>>(ifstream& is,array& vec); template ifstream& operator>>(ifstream& is,pair& p); template ifstream& operator>>(ifstream& is,vector& vec){ for(T& x: vec) is>>x;return is; } template ifstream& operator>>(ifstream& is,pair& p){ is>>p.first;is>>p.second;return is; } inline void fin(){} template inline void fin(Head&& head,Tail&&... tail){ infile>>head;fin(move(tail)...); } */ //#include HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); inline void in(){ SetConsoleTextAttribute(hConsole,10); } template inline void in(Head&& head,Tail&&... tail){ SetConsoleTextAttribute(hConsole,15); cin>>head;in(move(tail)...); } #else inline void in(){} template inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); } #endif inline bool out(){ return(cout<<'\n',0); } template inline bool out(T t){ return(cout< inline bool out(Head head,Tail... tail){ cout< inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); } #define alc alloc #ifdef _ENV_TQK_ inline bool deb(){ SetConsoleTextAttribute(hConsole,10); return(cout<<'\n',0); } template inline bool deb(T t){ return(SetConsoleTextAttribute(hConsole,12),cout< inline bool deb(Head head,Tail... tail){ SetConsoleTextAttribute(hConsole,12); cout< name(size);in(name) #define pb push_back #define fi e.first #define se e.second #define YES(c) cout<<((c)?"YES\n":"NO\n"),0 #define Yes(c) cout<<((c)?"Yes\n":"No\n"),0 #define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0 #define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0 #define o(p) cout<r)swap(l,r); #define fn(ty1,ty2,ex) [&](ty1 l,ty2 r){ return(ex); } #define lfn(ex) [&](lint l,lint r){ return(ex); } // #pragma endregion // #pragma region func inline constexpr lint gcd(lint a,lint b){ while(b){ lint c=b;b=a%b;a=c; }return a; } inline constexpr lint lcm(lint a,lint b){ return a/gcd(a,b)*b; } template inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; } template inline constexpr bool chmax(T &mx,const T &cnt){ if(mx inline void srt(F f){ } template inline void srt(F f,Head&& head,Tail&&... tail){ vectora(head.size()); iota(all(a),0); sort(all(a),f); auto res=head; rep(head.size())res[i]=head[a[i]]; head=res; srt(f,move(tail)...); } auto smaller(vector&a){ return [&](int i,int j){return a[i]&a){ return [&](int i,int j){return a[i]>a[j];}; } // #pragma endregion // #pragma region P class P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; }; istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; } inline constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); } inline constexpr bool operator==(const P& l,const P& r){ return(l.f==r.f&&l.s==r.s); } inline constexpr bool operator!=(const P& l,const P& r){ return(l.f!=r.f||l.s!=r.s); } inline P operator+(const P& l,const P& r){return P(l.f+r.f,l.s+r.s);} inline P operator-(const P& l,const P& r){return P(l.f-r.f,l.s-r.s);} inline P operator-(const P& r){return P(-r.f,-r.s); } inline P operator*(const lint& l,const P& r){return P(l*r.f,l*r.s); } inline P operator/(const P& l,const lint& r){return P(l.f/r,l.s/r); } inline ld abs(P p){return sqrtl(p.f*p.f+p.s*p.s);} inline ld mabs(P p){return abs(p.f)+abs(p.s);} inline ld mht(P x,P y){return mabs(x-y);} // #pragma endregion // #pragma region start struct Start{ Start(){ #ifndef _C_INPUT_ cin.tie(0),cout.tie(0); ios::sync_with_stdio(0); #endif cout< struct Dinic { struct edge { int to; T cap; int rev; }; const T INF; vector< vector< edge > > graph; vector< T > min_cost; vector< int > iter; Dinic(int n): INF(numeric_limits< T >::max()) { graph.resize(n); } void add_edge(int from, int to, T cap) { graph[from].push_back({ to, cap, (int)graph[to].size() }); graph[to].push_back({ from, 0, (int)graph[from].size()-1 }); } bool bfs(int s, int t) { min_cost.assign(graph.size(), -1); queue< int > que; min_cost[s] = 0; que.push(s); while(!que.empty()) { int p = que.front(); que.pop(); for(auto& e:graph[p]) { if(e.cap>0&&min_cost[e.to]==-1) { min_cost[e.to] = min_cost[p]+1; que.push(e.to); } } } return (min_cost[t]!=-1); } T dfs(int idx, const int t, T flow) { if(idx==t) return (flow); for(int& i = iter[idx]; i0&&min_cost[idx]0) { e.cap -= d; graph[e.to][e.rev].cap += d; return (d); } } } return (0); } T max_flow(int s, int t) { T flow = 0; while(bfs(s, t)) { iter.assign(graph.size(), 0); T f = 0; while((f = dfs(s, t, INF))>0) { flow += f; } } return (flow); } }; // #pragma endregion int solve(){ lin(h, w); vector> g(h, vector(w)); rep(h)in(g[i]); vin(lint, r, h); vin(lint, c, w); each(r)e *= 2; each(c)e *= 2; Dinic d(h+w+2); rep(h)rep(j, w){ d.add_edge(0, 1+i, g[i][j]); d.add_edge(0, 1+h+j, g[i][j]); d.add_edge(1+i, 1+h+j, g[i][j]); d.add_edge(1+h+j, 1+i, g[i][j]); } rep(h)d.add_edge(1+i, 1+h+w, r[i]); rep(j, w)d.add_edge(1+h+j, 1+h+w, c[j]); lint ans = 0; each(r)ans += e; each(c)ans += e; ans -= d.max_flow(0, 1+h+w); out(ans/2); return 0; } // #pragma endregion // #pragma region main int main(){ solve(); } // #pragma endregion //sub-EOF