#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

struct flow_network {
	struct edge { ll to, cap, cost; };

	ll n, s, t;
	vvl adj;
	vector<edge> e;
	
	flow_network(ll n, ll s, ll t): n(n), s(s), t(t), adj(n) { }

	void add_edge(ll a, ll b, ll cap, ll cost) {
		adj[a].pb(sz(e));
		e.pb({b,cap,cost});
		adj[b].pb(sz(e));
		e.pb({a,0,-cost});
	}

	pll mcmf() {
		vl pot(n);
		FOR(t,0,n) FOR(i,0,n) for (ll k: adj[i]) if (e[k].cap) {
			pot[e[k].to] = min(pot[e[k].to],pot[i] + e[k].cost);
		}
		ll flow = 0, cost = 0;
		while (true) {
			vl dist(n,oo), pred(n);
			set<pll> q;
			dist[s] = 0, q.insert({0,s});
			while (sz(q)) {
				ll i = begin(q)->yy;
				q.erase(begin(q));
				for (ll k: adj[i]) if (e[k].cap) {
					ll j = e[k].to, ndist = dist[i] + e[k].cost + pot[i] - pot[j];
					if (ndist >= dist[j]) continue;
					q.erase({dist[j],j});
					dist[j] = ndist, pred[j] = k;
					q.insert({dist[j],j});
				}
			}
			if (dist[t] == oo) break;

			ll cap = oo, cost1 = 0;
			for (ll i = t; i != s; i = e[pred[i]^1].to) {
				cap = min(cap,e[pred[i]].cap), cost1 += e[pred[i]].cost;
			}
			flow += cap, cost += cap*cost1;
			for (ll i = t; i != s; i = e[pred[i]^1].to) {
				e[pred[i]].cap -= cap, e[pred[i]^1].cap += cap;
			}
			FOR(i,0,n) pot[i] += dist[i];
		}
		return {flow,cost};
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	ll N = 2*n+6, s = N-2, t = N-1;
	flow_network F(N,s,t);
	
	FOR(i,0,n) {
		ll x, y, c;
		cin >> x >> y >> c;
		
		F.add_edge(s,i,c,0);
		F.add_edge(i,2*n+0,oo, x+y);
		F.add_edge(i,2*n+1,oo,-x+y);
		F.add_edge(i,2*n+2,oo, x-y);
		F.add_edge(i,2*n+3,oo,-x-y);
	}
	
	FOR(i,0,n) {
		ll x, y, c;
		cin >> x >> y >> c;

		F.add_edge(n+i,t,c,0);
		F.add_edge(2*n+0,n+i,oo,-x-y);
		F.add_edge(2*n+1,n+i,oo, x-y);
		F.add_edge(2*n+2,n+i,oo,-x+y);
		F.add_edge(2*n+3,n+i,oo, x+y);
	}

	pll res = F.mcmf();
	cerr << res.xx << endl;
	cout << -res.yy << endl;
	
}


### Prompt

Construct a CPP code solution to the problem outlined:

Snuke is playing with red and blue balls, placing them on a two-dimensional plane.

First, he performed N operations to place red balls. In the i-th of these operations, he placed RC_i red balls at coordinates (RX_i,RY_i). Then, he performed another N operations to place blue balls. In the i-th of these operations, he placed BC_i blue balls at coordinates (BX_i,BY_i). The total number of red balls placed and the total number of blue balls placed are equal, that is, \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i. Let this value be S.

Snuke will now form S pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the score of a pair of a red ball at coordinates (rx, ry) and a blue ball at coordinates (bx, by) as |rx-bx| + |ry-by|.

Snuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.

Constraints

* 1 \leq N \leq 1000
* 0 \leq RX_i,RY_i,BX_i,BY_i \leq 10^9
* 1 \leq RC_i,BC_i \leq 10
* \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
RX_1 RY_1 RC_1
RX_2 RY_2 RC_2
\vdots
RX_N RY_N RC_N
BX_1 BY_1 BC_1
BX_2 BY_2 BC_2
\vdots
BX_N BY_N BC_N


Output

Print the maximum possible sum of the scores of the pairs.

Examples

Input

2
0 0 1
3 2 1
2 2 1
5 0 1


Output

8


Input

3
0 0 1
2 2 1
0 0 2
1 1 1
1 1 1
3 3 2


Output

16


Input

10
582463373 690528069 8
621230322 318051944 4
356524296 974059503 6
372751381 111542460 9
392867214 581476334 6
606955458 513028121 5
882201596 791660614 9
250465517 91918758 3
618624774 406956634 6
426294747 736401096 5
974896051 888765942 5
726682138 336960821 3
715144179 82444709 6
599055841 501257806 6
390484433 962747856 4
912334580 219343832 8
570458984 648862300 6
638017635 572157978 10
435958984 585073520 7
445612658 234265014 6


Output

45152033546

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

struct flow_network {
	struct edge { ll to, cap, cost; };

	ll n, s, t;
	vvl adj;
	vector<edge> e;
	
	flow_network(ll n, ll s, ll t): n(n), s(s), t(t), adj(n) { }

	void add_edge(ll a, ll b, ll cap, ll cost) {
		adj[a].pb(sz(e));
		e.pb({b,cap,cost});
		adj[b].pb(sz(e));
		e.pb({a,0,-cost});
	}

	pll mcmf() {
		vl pot(n);
		FOR(t,0,n) FOR(i,0,n) for (ll k: adj[i]) if (e[k].cap) {
			pot[e[k].to] = min(pot[e[k].to],pot[i] + e[k].cost);
		}
		ll flow = 0, cost = 0;
		while (true) {
			vl dist(n,oo), pred(n);
			set<pll> q;
			dist[s] = 0, q.insert({0,s});
			while (sz(q)) {
				ll i = begin(q)->yy;
				q.erase(begin(q));
				for (ll k: adj[i]) if (e[k].cap) {
					ll j = e[k].to, ndist = dist[i] + e[k].cost + pot[i] - pot[j];
					if (ndist >= dist[j]) continue;
					q.erase({dist[j],j});
					dist[j] = ndist, pred[j] = k;
					q.insert({dist[j],j});
				}
			}
			if (dist[t] == oo) break;

			ll cap = oo, cost1 = 0;
			for (ll i = t; i != s; i = e[pred[i]^1].to) {
				cap = min(cap,e[pred[i]].cap), cost1 += e[pred[i]].cost;
			}
			flow += cap, cost += cap*cost1;
			for (ll i = t; i != s; i = e[pred[i]^1].to) {
				e[pred[i]].cap -= cap, e[pred[i]^1].cap += cap;
			}
			FOR(i,0,n) pot[i] += dist[i];
		}
		return {flow,cost};
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	ll N = 2*n+6, s = N-2, t = N-1;
	flow_network F(N,s,t);
	
	FOR(i,0,n) {
		ll x, y, c;
		cin >> x >> y >> c;
		
		F.add_edge(s,i,c,0);
		F.add_edge(i,2*n+0,oo, x+y);
		F.add_edge(i,2*n+1,oo,-x+y);
		F.add_edge(i,2*n+2,oo, x-y);
		F.add_edge(i,2*n+3,oo,-x-y);
	}
	
	FOR(i,0,n) {
		ll x, y, c;
		cin >> x >> y >> c;

		F.add_edge(n+i,t,c,0);
		F.add_edge(2*n+0,n+i,oo,-x-y);
		F.add_edge(2*n+1,n+i,oo, x-y);
		F.add_edge(2*n+2,n+i,oo,-x+y);
		F.add_edge(2*n+3,n+i,oo, x+y);
	}

	pll res = F.mcmf();
	cerr << res.xx << endl;
	cout << -res.yy << endl;
	
}


```