#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;
    }
};