#include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair< int, int >; using pll = pair< ll, ll >; template< class T > using vc = vector< T >; template< class T > using vvc = vector< vector< T > >; template< class T > using vvvc = vector< vector< vector< T > > >; template< class T > using vvvvc = vector< vector< vector< vector< T > > > >; template< class T > using pq = priority_queue< T >; template< class T > using pqg = priority_queue< T, vector< T >, greater< T > >; template< class T > using mset = multiset< T >; template< class T > using uset = unordered_set< T >; template< class T, class U > using umap = unordered_map< T, U >; template< class T > struct Edge { int from, to; T cost; int id; Edge( int from_, int to_, T cost_ = 1, int id_ = -1 ) : from( from_ ), to( to_ ), cost( cost_ ), id( id_ ) {} }; template< class T > struct Graph { vector< vector< Edge< T > > > G; int e; bool is_directed; Graph() {} Graph( int n, bool is_directed_ = false ) : G( n ), e( 0 ), is_directed( is_directed_ ) {} int size() const { return G.size(); } void add_edge( int from, int to, T cost = 1 ) { G[ from ].emplace_back( from, to, cost, e ); if ( !is_directed ) G[ to ].emplace_back( to, from, cost, e ); e++; } void add_edge( int from, int to, T cost, int id ) { G[ from ].emplace_back( from, to, cost, id ); if ( !is_directed ) G[ to ].emplace_back( to, from, cost, id ); e++; } inline vector< Edge< T > > &operator[]( int i ) { return G[ i ]; } }; template< class T > using Edges = vector< Edge< T > >; #define vec( type, name, ... ) vector< type > name( __VA_ARGS__ ) #define vv( type, name, h, ... ) vector name( h, vector< type >( __VA_ARGS__ ) ) #define vvv( type, name, h, w, ... ) vector name( h, vector( w, vector< type >( __VA_ARGS__ ) ) ) #define vvvv( type, name, a, b, c, ... ) vector< vector< vector< vector< type > > > > name( a, vector< vector< vector< type > > >( b, vector< vector< type > >( c, vector< type >( __VA_ARGS__ ) ) ) ) const int INF = 0x3fffffff; const ll LINF = 0x1fffffffffffffff; const ld DINF = numeric_limits< ld >::infinity(); const ld EPS = 1e-10; const ld PI = 3.1415926535897932; const ll dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 }; const ll dy[] = { 1, 0, -1, 0, 1, 1, -1, -1 }; #define overload5( a, b, c, d, e, name, ... ) name #define overload4( a, b, c, d, name, ... ) name #define overload3( a, b, c, name, ... ) name #define rep0( n ) for ( ll qwerty = 0; qwerty < n; qwerty++ ) #define rep1( i, n ) for ( ll i = 0; i < ( n ); i++ ) #define rep2( i, a, b ) for ( ll i = ( a ); i < ( b ); i++ ) #define rep3( i, a, b, c ) for ( ll i = ( a ); i < ( b ); i += ( c ) ) #define rep( ... ) overload4( __VA_ARGS__, rep3, rep2, rep1, rep0 )( __VA_ARGS__ ) #define rrep0( n ) for ( ll qwerty = (n)-1; qwerty >= 0; qwerty-- ) #define rrep1( i, n ) for ( ll i = (n)-1; i >= 0; i-- ) #define rrep2( i, a, b ) for ( ll i = (a)-1; i >= ( b ); i-- ) #define rrep3( i, a, b, c ) for ( ll i = (a)-1; i >= ( b ); i -= ( c ) ) #define rrep( ... ) overload4( __VA_ARGS__, rrep3, rrep2, rrep1, rrep0 )( __VA_ARGS__ ) #define each1( i, a ) for ( auto &&i : a ) #define each2( x, y, a ) for ( auto &&[ x, y ] : a ) #define each3( x, y, z, a ) for ( auto &&[ x, y, z ] : a ) #define each4( w, x, y, z, a ) for ( auto &&[ w, x, y, z ] : a ) #define each( ... ) overload5( __VA_ARGS__, each4, each3, each2, each1 )( __VA_ARGS__ ) #define all1( i ) begin( i ), end( i ) #define all2( i, a ) begin( i ), begin( i ) + a #define all3( i, a, b ) begin( i ) + a, begin( i ) + b #define all( ... ) overload3( __VA_ARGS__, all3, all2, all1 )( __VA_ARGS__ ) #define rall1( i ) rbegin( i ), rend( i ) #define rall2( i, a ) rbegin( i ), rbegin( i ) + a #define rall3( i, a, b ) rbegin( i ) + a, rbegin( i ) + b #define rall( ... ) overload3( __VA_ARGS__, rall3, rall2, rall1 )( __VA_ARGS__ ) #define fi first #define se second #define pb push_back #define eb emplace_back #define Endl '\n' #define ifnot( x ) if ( !( x ) ) #define YesNo( x ) cout << ( x ? "Yes" : "No" ) << endl; #define bit( i ) ( 1LL << ( i ) ) #define getbit( x, i ) ( ( ( x ) >> ( i ) ) & 1 ) #define topbit( x ) ( ( x ) == 0 ? -1 : 63 - __builtin_clzll( x ) ) #define lowbit( x ) ( ( x ) == 0 ? 64 : __builtin_ctzll( x ) ) #define popcount( x ) __builtin_popcountll( x ) #define mask( i ) ( ( 1LL << ( i ) ) - 1 ) template< class T > vector< T > &operator++( vector< T > &v ) { for ( auto &e : v ) e++; return v; } template< class T > vector< T > operator++( vector< T > &v, signed ) { auto res = v; for ( auto &e : v ) e++; return res; } template< class T > vector< T > &operator--( vector< T > &v ) { for ( auto &e : v ) e--; return v; } template< class T > vector< T > operator--( vector< T > &v, signed ) { auto res = v; for ( auto &e : v ) e--; return res; } template< class T, class U > istream &operator>>( istream &is, pair< T, U > &p ) { is >> p.first >> p.second; return is; } template< class T, class U > ostream &operator<<( ostream &os, const pair< T, U > &p ) { os << p.first << ' ' << p.second; return os; } template< class T > istream &operator>>( istream &is, vector< T > &v ) { for ( auto &e : v ) is >> e; return is; } template< class T > ostream &operator<<( ostream &os, const vector< T > &v ) { for ( auto &e : v ) os << e << ' '; return os; } template< class T > ostream &operator<<( ostream &os, const vector< vector< T > > &v ) { for ( auto &e : v ) { for ( auto &c : e ) os << c << ' '; os << endl; } return os; } #define INT( ... ) \ int __VA_ARGS__; \ IN( __VA_ARGS__ ) #define INTd( ... ) \ int __VA_ARGS__; \ IN2( __VA_ARGS__ ) #define LL( ... ) \ ll __VA_ARGS__; \ IN( __VA_ARGS__ ) #define LLd( ... ) \ ll __VA_ARGS__; \ IN2( __VA_ARGS__ ) #define STR( ... ) \ string __VA_ARGS__; \ IN( __VA_ARGS__ ) #define CHR( ... ) \ char __VA_ARGS__; \ IN( __VA_ARGS__ ) #define DBL( ... ) \ double __VA_ARGS__; \ IN( __VA_ARGS__ ) #define LD( ... ) \ long double __VA_ARGS__; \ IN( __VA_ARGS__ ) #define VEC( type, name, size ) \ vector< type > name( size ); \ IN( name ) #define VECd( type, name, size ) \ vector< type > name( size ); \ IN2( name ) #define VEC2( type, name1, name2, size ) \ vector< type > name1( size ), name2( size ); \ for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ] ) #define VEC2d( type, name1, name2, size ) \ vector< type > name1( size ), name2( size ); \ for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ] ) #define VEC3( type, name1, name2, name3, size ) \ vector< type > name1( size ), name2( size ), name3( size ); \ for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ], name3[ i ] ) #define VEC3d( type, name1, name2, name3, size ) \ vector< type > name1( size ), name2( size ), name3( size ); \ for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ], name3[ i ] ) #define VEC4( type, name1, name2, name3, name4, size ) \ vector< type > name1( size ), name2( size ), name3( size ), name4( size ); \ for ( int i = 0; i < size; i++ ) IN( name1[ i ], name2[ i ], name3[ i ], name4[ i ] ); #define VEC4d( type, name1, name2, name3, name4, size ) \ vector< type > name1( size ), name2( size ), name3( size ), name4( size ); \ for ( int i = 0; i < size; i++ ) IN2( name1[ i ], name2[ i ], name3[ i ], name4[ i ] ); #define VV( type, name, h, w ) \ vector< vector< type > > name( h, vector< type >( w ) ); \ IN( name ) #define VVd( type, name, h, w ) \ vector< vector< type > > name( h, vector< type >( w ) ); \ IN2( name ) int scan() { return getchar(); } void scan( int &a ) { cin >> a; } void scan( long long &a ) { cin >> a; } void scan( char &a ) { cin >> a; } void scan( double &a ) { cin >> a; } void scan( string &a ) { cin >> a; } template< class T, class S > void scan( pair< T, S > &p ) { scan( p.first ), scan( p.second ); } template< class T > void scan( vector< T > & ); template< class T > void scan( vector< T > &a ) { for ( auto &i : a ) scan( i ); } template< class T > void scan( T &a ) { cin >> a; } void IN() {} void IN2() {} template< class Head, class... Tail > void IN( Head &head, Tail &...tail ) { scan( head ); IN( tail... ); } template< class Head, class... Tail > void IN2( Head &head, Tail &...tail ) { scan( head ); --head; IN2( tail... ); } template< class T, class S > bool inc( const T &x, const S &l, const S &r ) { return l <= x && x < r; } template< typename T > int si( const T &x ) { return x.size(); } template< class T, class S > inline bool chmax( T &a, const S &b ) { return ( a < b ? a = b, 1 : 0 ); } template< class T, class S > inline bool chmin( T &a, const S &b ) { return ( a > b ? a = b, 1 : 0 ); } vector< int > iota( int n, int s = 0 ) { vector< int > ret( n ); iota( ret.begin(), ret.end(), s ); return ret; } template< class T > void sort( T &v ) { sort( v.begin(), v.end() ); } template< class T > void rsort( T &v ) { sort( v.rbegin(), v.rend() ); } template< class T > void reverse( T &v ) { reverse( v.begin(), v.end() ); } template< class T > auto max( const T &a ) { return *max_element( a.begin(), a.end() ); } template< class T > auto min( const T &a ) { return *min_element( a.begin(), a.end() ); } template< class T > int max_id( const T &a ) { return max_element( a.begin(), a.end() ) - a.begin(); } template< class T > int min_id( const T &a ) { return min_element( a.begin(), a.end() ) - a.begin(); } template< class T, class S > int lb( vector< T > &v, S a ) { return lower_bound( v.begin(), v.end(), (T)a ) - v.begin(); } template< class T, class S > int ub( vector< T > &v, S a ) { return upper_bound( v.begin(), v.end(), (T)a ) - v.begin(); } template< typename T = ll, typename S > T sum( const S &v ) { return accumulate( v.begin(), v.end(), T( 0 ) ); } template< class T > vector< T > uniq( vector< T > v ) { sort( v.begin(), v.end() ); v.erase( unique( v.begin(), v.end() ), v.end() ); return v; } long long max( int x, long long y ) { return max( (long long)x, y ); } long long max( long long x, int y ) { return max( x, (long long)y ); } long long min( int x, long long y ) { return min( (long long)x, y ); } long long min( long long x, int y ) { return min( x, (long long)y ); } template< class T, class S > T floor( T x, S y ) { if ( y < 0 ) x = -x, y = -y; return ( x >= 0 ? x / y : ( x - y + 1 ) / y ); } template< class T, class S > T ceil( T x, S y ) { if ( y < 0 ) x = -x, y = -y; return ( x >= 0 ? ( x + y - 1 ) / y : x / y ); } template< class T > class Dinic { struct FlowEdge { int to; T cap; int rev; bool is_rev; int idx; FlowEdge( int to_, T cap_, int rev_, bool is_rev_, int idx_ ) : to( to_ ), cap( cap_ ), rev( rev_ ), is_rev( is_rev_ ), idx( idx_ ) {} }; bool bfs( int s, int t ) { min_cost.assign( N, -1 ); min_cost[ s ] = 0; queue< int > q; q.push( s ); while ( !q.empty() ) { int v = q.front(); q.pop(); for ( auto &e : G[ v ] ) { if ( e.cap > 0 && min_cost[ e.to ] == -1 ) { min_cost[ e.to ] = min_cost[ v ] + 1; q.push( e.to ); } } } return min_cost[ t ] != -1; } T dfs( int v, int t, T flow ) { if ( v == t ) return flow; for ( int &i = pos[ v ]; i < (int)G[ v ].size(); i++ ) { FlowEdge &e = G[ v ][ i ]; if ( e.cap > 0 && min_cost[ e.to ] > min_cost[ v ] ) { T f = dfs( e.to, t, min( flow, e.cap ) ); if ( f > 0 ) { e.cap -= f; G[ e.to ][ e.rev ].cap += f; return f; } } } return 0; } public: vector< vector< FlowEdge > > G; vector< int > min_cost, pos; const T INF_T; const int N; Dinic( int N_, T INF_T_ = numeric_limits< T >::max() / 2 ) : G( N_ ), min_cost( N_ ), pos( N_ ), INF_T( INF_T_ ), N( N_ ) {} void add_edge( int from, int to, T cap, int idx = -1 ) { G[ from ].emplace_back( to, cap, (int)G[ to ].size(), false, idx ); G[ to ].emplace_back( from, 0, (int)G[ from ].size() - 1, true, idx ); } // min_costが最小カットの1つ(0以上ならs側、-1ならt側) T max_flow( int s, int t ) { T flow = 0; while ( bfs( s, t ) ) { pos.assign( N, 0 ); T f; while ( ( f = dfs( s, t, INF_T ) ) > 0 ) flow += f; } return flow; } }; int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); cout << fixed << setprecision( 15 ); INT( H, W ); Dinic< ll > dinic( H * W + H + W + 2, LINF ); rep( i, H ) rep( j, W ) { LL( G ); dinic.add_edge( i * W + j, H * W + H + W + 1, G ); } ll sm = 0; rep( i, H ) { LL( R ); dinic.add_edge( H * W + H + W, H * W + i, R ); sm += R; } rep( j, W ) { LL( C ); dinic.add_edge( H * W + H + W, H * W + H + j, C ); sm += C; } rep( i, H ) rep( j, W ) { dinic.add_edge( H * W + i, i * W + j, LINF ); dinic.add_edge( H * W + H + j, i * W + j, LINF ); } cout << sm - dinic.max_flow( H * W + H + W, H * W + H + W + 1 ) << endl; }