#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i(a); i < (b); ++i)
#define PER(i,a,b) for(int i((a)-1); i >= (b); --i)
template < class T,class U>
bool cmax( T & a, const U & b) { return a < b ? a = b, 1 : 0 ; }
template < class T,class U>
bool cmin( T & a, const U & b) { return b < a ? a = b, 1 : 0 ; }
typedef long long ll;
typedef pair< int ,int > pii;
typedef pair< ll,ll> pll;
#define F first
#define S second
typedef vector< int > vi;
typedef vector< ll> vll;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define PB push_back
#define EB emplace_back
typedef pair< long long , long long > pll;
struct CostFlow {
static const int MXN = 205 ;
static const long long INF = 102938475610293847LL;
struct Edge {
int v, r;
long long f, c;
} ;
int n, s, t, prv[ MXN] , prvL[ MXN] , inq[ MXN] ;
long long dis[ MXN] , fl, cost;
vector< Edge> E[ MXN] ;
void init( int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for ( int i= 0 ; i< n; i++ ) E[ i] .clear ( ) ;
fl = cost = 0 ;
}
void add_edge( int u, int v, long long f, long long c) {
E[ u] .PB ( { v, SZ( E[ v] ) , f, c} ) ;
E[ v] .PB ( { u, SZ( E[ u] ) - 1 , 0 , - c} ) ;
}
pll flow( ) {
while ( true ) {
for ( int i= 0 ; i< n; i++ ) {
dis[ i] = INF;
inq[ i] = 0 ;
}
dis[ s] = 0 ;
queue< int > que;
que.push ( s) ;
while ( ! que.empty ( ) ) {
int u = que.front ( ) ; que.pop ( ) ;
inq[ u] = 0 ;
for ( int i= 0 ; i< SZ( E[ u] ) ; i++ ) {
int v = E[ u] [ i] .v ;
long long w = E[ u] [ i] .c ;
if ( E[ u] [ i] .f > 0 && dis[ v] > dis[ u] + w) {
prv[ v] = u; prvL[ v] = i;
dis[ v] = dis[ u] + w;
if ( ! inq[ v] ) {
inq[ v] = 1 ;
que.push ( v) ;
}
}
}
}
if ( dis[ t] == INF) break ;
long long tf = INF;
for ( int v= t, u, l; v! = s; v= u) {
u= prv[ v] ; l= prvL[ v] ;
tf = min( tf, E[ u] [ l] .f ) ;
}
for ( int v= t, u, l; v! = s; v= u) {
u= prv[ v] ; l= prvL[ v] ;
E[ u] [ l] .f - = tf;
E[ v] [ E[ u] [ l] .r ] .f + = tf;
}
cost + = tf * dis[ t] ;
fl + = tf;
}
return { fl, cost} ;
}
} flow;
int mx[ 205 ] , my[ 205 ] ;
void getmc( int n,int m)
{
fill_n( mx,n,- 1 ) ;
fill_n( my,m,- 1 ) ;
for ( int i = 0 ; i < n; ++ i)
for ( const auto & e : flow.E [ i] )
if ( e.f == 0 ) {
int j = e.v - n;
if ( 0 <= j && j < m)
mx[ i] = j, my[ j] = i;
}
}
class ShoppingSpree {
public :
int maxValue( int k, vector< int > a, vector< int > b, vector< int > x, vector< int > y) {
int n = a.size ( ) , m = b.size ( ) , d = x.size ( ) ;
int s0 = n + m, s1 = n + m + 1 , t = n + m + 2 ;
flow.init ( n+ m+ 3 ,s0,t) ;
for ( int i = 0 ; i < n; ++ i)
flow.add_edge ( s1,i,1 ,0 ) ;
for ( int i = 0 ; i < d; ++ i)
flow.add_edge ( x[ i] ,n+ y[ i] ,1 ,- ( a[ x[ i] ] + b[ y[ i] ] ) ) ;
for ( int i = 0 ; i < m; ++ i)
flow.add_edge ( n+ i,t,1 ,0 ) ;
int ret = 0 ;
for ( int j = 1 ; j <= k; ++ j) {
flow.add_edge ( s0,s1,1 ,0 ) ;
ll fl,co;
tie( fl,co) = flow.flow ( ) ;
getmc( n,m) ;
vector< pii> ve;
for ( int i = 0 ; i < d; ++ i) {
if ( mx[ x[ i] ] == - 1 && my[ y[ i] ] == - 1 )
continue ;
if ( mx[ x[ i] ] ! = - 1 && my[ y[ i] ] ! = - 1 )
continue ;
if ( mx[ x[ i] ] ! = - 1 ) {
ve.EB ( b[ y[ i] ] , n+ y[ i] ) ;
}
if ( my[ y[ i] ] ! = - 1 ) {
ve.EB ( a[ x[ i] ] , x[ i] ) ;
}
}
sort( ALL( ve) ,greater< pii> ( ) ) ;
int su = - co;
for ( int i = 0 ; i < k - j && i < ve.size ( ) ; ++ i)
su + = ve[ i] .F ;
//cerr << "su "<< su << endl;
ret = max( ret,su) ;
}
return ret;
}
} ;
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgUkVQKGksYSxiKSBmb3IgKGludCBpKGEpOyBpIDwgKGIpOyArK2kpCiNkZWZpbmUgUEVSKGksYSxiKSBmb3IoaW50IGkoKGEpLTEpOyBpID49IChiKTsgLS1pKQp0ZW1wbGF0ZTxjbGFzcyBULGNsYXNzIFU+CmJvb2wgY21heChUICYgYSwgY29uc3QgVSAmIGIpIHtyZXR1cm4gYSA8IGIgPyBhID0gYiwgMSA6IDA7fQp0ZW1wbGF0ZTxjbGFzcyBULGNsYXNzIFU+CmJvb2wgY21pbihUICYgYSwgY29uc3QgVSAmIGIpIHtyZXR1cm4gYiA8IGEgPyBhID0gYiwgMSA6IDA7fQp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbGw7CiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPGxsPiB2bGw7CiNkZWZpbmUgU1ooYSkgKChpbnQpKGEpLnNpemUoKSkKI2RlZmluZSBBTEwoYSkgYmVnaW4oYSksIGVuZChhKQojZGVmaW5lIFBCIHB1c2hfYmFjawojZGVmaW5lIEVCIGVtcGxhY2VfYmFjawp0eXBlZGVmIHBhaXI8bG9uZyBsb25nLCBsb25nIGxvbmc+IHBsbDsKc3RydWN0IENvc3RGbG93IHsKCXN0YXRpYyBjb25zdCBpbnQgTVhOID0gMjA1OwoJc3RhdGljIGNvbnN0IGxvbmcgbG9uZyBJTkYgPSAxMDI5Mzg0NzU2MTAyOTM4NDdMTDsKCXN0cnVjdCBFZGdlIHsKCQlpbnQgdiwgcjsKCQlsb25nIGxvbmcgZiwgYzsKCX07CglpbnQgbiwgcywgdCwgcHJ2W01YTl0sIHBydkxbTVhOXSwgaW5xW01YTl07Cglsb25nIGxvbmcgZGlzW01YTl0sIGZsLCBjb3N0OwoJdmVjdG9yPEVkZ2U+IEVbTVhOXTsKCXZvaWQgaW5pdChpbnQgX24sIGludCBfcywgaW50IF90KSB7CgkJbiA9IF9uOyBzID0gX3M7IHQgPSBfdDsKCQlmb3IgKGludCBpPTA7IGk8bjsgaSsrKSBFW2ldLmNsZWFyKCk7CgkJZmwgPSBjb3N0ID0gMDsKCX0KCXZvaWQgYWRkX2VkZ2UoaW50IHUsIGludCB2LCBsb25nIGxvbmcgZiwgbG9uZyBsb25nIGMpIHsKCQlFW3VdLlBCKHt2LCBTWihFW3ZdKSAgLCBmLCAgY30pOwoJCUVbdl0uUEIoe3UsIFNaKEVbdV0pLTEsIDAsIC1jfSk7Cgl9CglwbGwgZmxvdygpIHsKICAgICAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgICAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSB7CiAgICAgICAgICAgICAgICBkaXNbaV0gPSBJTkY7CiAgICAgICAgICAgICAgICBpbnFbaV0gPSAwOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGRpc1tzXSA9IDA7CgkJCXF1ZXVlPGludD4gcXVlOwoJCQlxdWUucHVzaChzKTsKCQkJd2hpbGUgKCFxdWUuZW1wdHkoKSkgewoJCQkJaW50IHUgPSBxdWUuZnJvbnQoKTsgcXVlLnBvcCgpOwoJCQkJaW5xW3VdID0gMDsKCQkJCWZvciAoaW50IGk9MDsgaTxTWihFW3VdKTsgaSsrKSB7CgkJCQkJaW50IHYgPSBFW3VdW2ldLnY7CgkJCQkJbG9uZyBsb25nIHcgPSBFW3VdW2ldLmM7CgkJCQkJaWYgKEVbdV1baV0uZiA+IDAgJiYgZGlzW3ZdID4gZGlzW3VdICsgdykgewoJCQkJCQlwcnZbdl0gPSB1OyBwcnZMW3ZdID0gaTsKCQkJCQkJZGlzW3ZdID0gZGlzW3VdICsgdzsKCQkJCQkJaWYgKCFpbnFbdl0pIHsKCQkJCQkJCWlucVt2XSA9IDE7CgkJCQkJCQlxdWUucHVzaCh2KTsKCQkJCQkJfQoJCQkJCX0KCQkJCX0KCQkJfQoJCQlpZiAoZGlzW3RdID09IElORikgYnJlYWs7CgkJCWxvbmcgbG9uZyB0ZiA9IElORjsKCQkJZm9yIChpbnQgdj10LCB1LCBsOyB2IT1zOyB2PXUpIHsKCQkJCXU9cHJ2W3ZdOyBsPXBydkxbdl07CgkJCQl0ZiA9IG1pbih0ZiwgRVt1XVtsXS5mKTsKCQkJfQoJCQlmb3IgKGludCB2PXQsIHUsIGw7IHYhPXM7IHY9dSkgewoJCQkJdT1wcnZbdl07IGw9cHJ2TFt2XTsKCQkJCUVbdV1bbF0uZiAtPSB0ZjsKCQkJCUVbdl1bRVt1XVtsXS5yXS5mICs9IHRmOwoJCQl9CgkJCWNvc3QgKz0gdGYgKiBkaXNbdF07CgkJCWZsICs9IHRmOwoJCX0KCQlyZXR1cm4ge2ZsLCBjb3N0fTsKCX0KfWZsb3c7CmludCBteFsyMDVdLCBteVsyMDVdOwp2b2lkIGdldG1jKGludCBuLGludCBtKQp7CiAgICBmaWxsX24obXgsbiwtMSk7CiAgICBmaWxsX24obXksbSwtMSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKICAgICAgICBmb3IgKGNvbnN0IGF1dG8gJiAgZSA6IGZsb3cuRVtpXSkKICAgICAgICAgICAgaWYgKGUuZiA9PSAwKSB7CiAgICAgICAgICAgICAgICBpbnQgaiA9IGUudiAtIG47CiAgICAgICAgICAgICAgICBpZiAoMCA8PSBqICYmIGogPCBtKQogICAgICAgICAgICAgICAgICAgIG14W2ldID0gaiwgbXlbal0gPSBpOwogICAgICAgICAgICB9Cn0KY2xhc3MgU2hvcHBpbmdTcHJlZSB7CiAgICBwdWJsaWM6CiAgICBpbnQgbWF4VmFsdWUoaW50IGssIHZlY3RvcjxpbnQ+IGEsIHZlY3RvcjxpbnQ+IGIsIHZlY3RvcjxpbnQ+IHgsIHZlY3RvcjxpbnQ+IHkpIHsKICAgICAgICBpbnQgbiA9IGEuc2l6ZSgpLCBtID0gYi5zaXplKCksIGQgPSB4LnNpemUoKTsKICAgICAgICBpbnQgczAgPSBuICsgbSwgczEgPSBuICsgbSArIDEsIHQgPSBuICsgbSArIDI7CiAgICAgICAgZmxvdy5pbml0KG4rbSszLHMwLHQpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgICAgICBmbG93LmFkZF9lZGdlKHMxLGksMSwwKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGQ7ICsraSkKICAgICAgICAgICAgZmxvdy5hZGRfZWRnZSh4W2ldLG4reVtpXSwxLC0oYVt4W2ldXStiW3lbaV1dKSk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBtOyArK2kpCiAgICAgICAgICAgIGZsb3cuYWRkX2VkZ2UobitpLHQsMSwwKTsKICAgICAgICBpbnQgcmV0ID0gMDsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBrOyArK2opIHsKICAgICAgICAgICAgZmxvdy5hZGRfZWRnZShzMCxzMSwxLDApOwogICAgICAgICAgICBsbCBmbCxjbzsKICAgICAgICAgICAgdGllKGZsLGNvKSA9IGZsb3cuZmxvdygpOwogICAgICAgICAgICBnZXRtYyhuLG0pOwogICAgICAgICAgICB2ZWN0b3I8cGlpPiB2ZTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBkOyArK2kpIHsKICAgICAgICAgICAgICAgIGlmIChteFt4W2ldXSA9PSAtMSAmJiBteVt5W2ldXSA9PSAtMSkKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIGlmIChteFt4W2ldXSAhPSAtMSAmJiBteVt5W2ldXSAhPSAtMSkKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIGlmIChteFt4W2ldXSAhPSAtMSkgewogICAgICAgICAgICAgICAgICAgIHZlLkVCKGJbeVtpXV0sIG4reVtpXSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZiAobXlbeVtpXV0gIT0gLTEpIHsKICAgICAgICAgICAgICAgICAgICB2ZS5FQihhW3hbaV1dLCB4W2ldKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBzb3J0KEFMTCh2ZSksZ3JlYXRlcjxwaWk+KCkpOwogICAgICAgICAgICBpbnQgc3UgPSAtY287CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgayAtIGogJiYgaSA8IHZlLnNpemUoKTsgKytpKQogICAgICAgICAgICAgICAgc3UgKz0gdmVbaV0uRjsKICAgICAgICAgICAgLy9jZXJyIDw8ICJzdSAiPDwgc3UgPDwgZW5kbDsKICAgICAgICAgICAgcmV0ID0gbWF4KHJldCxzdSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXQ7CiAgICB9Cn07