#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int INF = (1<<30);
const ll inf = 1E15;

struct FlowGraph{
	#define MAXV (2500)
	#define MAXE (20*MAXV)
	struct edge{
		int to, cap, flow; ll cost;
		edge *nxt, *rev;
	}edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt;
	FlowGraph() {ecnt = edges;}
	void addedge(int u, int v, int c, ll w) {
		edge *p = (++ecnt), *q = (++ecnt);
		p->to = v, p->cap = c, p->flow = 0, p->cost = w;
		p->nxt = adj[u], adj[u] = p;
		q->to = u, q->cap = 0, q->flow = 0, q->cost = -w;
		q->nxt = adj[v], adj[v] = q;
		p->rev = q, q->rev = p;
	}
	int s, t;
	int hp[MAXV + 5]; ll f[MAXV + 5];
	void update(int x, ll k) {
		f[x] = k;
		while( x ) {
			hp[x] = x;
			if( (x<<1) <= t && f[hp[x<<1]] < f[hp[x]] )
				hp[x] = hp[x<<1];
			if( (x<<1|1) <= t && f[hp[x<<1|1]] < f[hp[x]] )
				hp[x] = hp[x<<1|1];
			x >>= 1;
		}
	}
	ll d[MAXV + 5], h[MAXV + 5];
	bool relabel() {
		for(int i=1;i<=t;i++)
			h[i] += d[i], d[i] = f[i] = inf, hp[i] = i, cur[i] = adj[i];
		update(s, d[s] = 0);
		while( f[hp[1]] != inf ) {
			int x = hp[1]; update(x, inf);
			for(edge *p=adj[x];p;p=p->nxt) {
				ll dis = d[x] + p->cost + (h[x] - h[p->to]);
				if( p->cap > p->flow && dis < d[p->to] )
					update(p->to, d[p->to] = dis);
			}
		}
		return !(d[t] == inf);
	}
	bool vis[MAXV + 5];
	int aug(int x, int tot) {
		if( x == t ) return tot;
		int sum = 0; vis[x] = true;
		for(edge *&p=cur[x];p;p=p->nxt) {
			ll dis = d[x] + p->cost + (h[x] - h[p->to]);
			if( !vis[p->to] && p->cap > p->flow && dis == d[p->to] ) {
				int del = aug(p->to, min(tot - sum, p->cap - p->flow));
				p->flow += del, p->rev->flow -= del, sum += del;
				if( sum == tot ) break;
			}
		}
		vis[x] = false;
		return sum;
	}
	ll min_cost_max_flow(int _s, int _t) {
		s = _s, t = _t; ll cost = 0;
		while( relabel() ) {
			int del = aug(s, INF);
			cost += del*(d[t] + h[t]);
		}
		return cost;
	}
}G;

int main() {
	int N; scanf("%d", &N);
	int s = 2*N + 4 + 1, t = 2*N + 4 + 2;
	for(int i=1;i<=N;i++) {
		int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
		G.addedge(s, i, C, 0);
		G.addedge(i, 2*N + 1, INF, + X + Y);
		G.addedge(i, 2*N + 2, INF, - X + Y);
		G.addedge(i, 2*N + 3, INF, + X - Y);
		G.addedge(i, 2*N + 4, INF, - X - Y);
	}
	for(int i=N+1;i<=2*N;i++) {
		int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
		G.addedge(i, t, C, 0);
		G.addedge(2*N + 1, i, INF, - X - Y);
		G.addedge(2*N + 2, i, INF, + X - Y);
		G.addedge(2*N + 3, i, INF, - X + Y);
		G.addedge(2*N + 4, i, INF, + X + Y);
	}
	printf("%lld\n", -G.min_cost_max_flow(s, t));
}
### 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 <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int INF = (1<<30);
const ll inf = 1E15;

struct FlowGraph{
	#define MAXV (2500)
	#define MAXE (20*MAXV)
	struct edge{
		int to, cap, flow; ll cost;
		edge *nxt, *rev;
	}edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt;
	FlowGraph() {ecnt = edges;}
	void addedge(int u, int v, int c, ll w) {
		edge *p = (++ecnt), *q = (++ecnt);
		p->to = v, p->cap = c, p->flow = 0, p->cost = w;
		p->nxt = adj[u], adj[u] = p;
		q->to = u, q->cap = 0, q->flow = 0, q->cost = -w;
		q->nxt = adj[v], adj[v] = q;
		p->rev = q, q->rev = p;
	}
	int s, t;
	int hp[MAXV + 5]; ll f[MAXV + 5];
	void update(int x, ll k) {
		f[x] = k;
		while( x ) {
			hp[x] = x;
			if( (x<<1) <= t && f[hp[x<<1]] < f[hp[x]] )
				hp[x] = hp[x<<1];
			if( (x<<1|1) <= t && f[hp[x<<1|1]] < f[hp[x]] )
				hp[x] = hp[x<<1|1];
			x >>= 1;
		}
	}
	ll d[MAXV + 5], h[MAXV + 5];
	bool relabel() {
		for(int i=1;i<=t;i++)
			h[i] += d[i], d[i] = f[i] = inf, hp[i] = i, cur[i] = adj[i];
		update(s, d[s] = 0);
		while( f[hp[1]] != inf ) {
			int x = hp[1]; update(x, inf);
			for(edge *p=adj[x];p;p=p->nxt) {
				ll dis = d[x] + p->cost + (h[x] - h[p->to]);
				if( p->cap > p->flow && dis < d[p->to] )
					update(p->to, d[p->to] = dis);
			}
		}
		return !(d[t] == inf);
	}
	bool vis[MAXV + 5];
	int aug(int x, int tot) {
		if( x == t ) return tot;
		int sum = 0; vis[x] = true;
		for(edge *&p=cur[x];p;p=p->nxt) {
			ll dis = d[x] + p->cost + (h[x] - h[p->to]);
			if( !vis[p->to] && p->cap > p->flow && dis == d[p->to] ) {
				int del = aug(p->to, min(tot - sum, p->cap - p->flow));
				p->flow += del, p->rev->flow -= del, sum += del;
				if( sum == tot ) break;
			}
		}
		vis[x] = false;
		return sum;
	}
	ll min_cost_max_flow(int _s, int _t) {
		s = _s, t = _t; ll cost = 0;
		while( relabel() ) {
			int del = aug(s, INF);
			cost += del*(d[t] + h[t]);
		}
		return cost;
	}
}G;

int main() {
	int N; scanf("%d", &N);
	int s = 2*N + 4 + 1, t = 2*N + 4 + 2;
	for(int i=1;i<=N;i++) {
		int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
		G.addedge(s, i, C, 0);
		G.addedge(i, 2*N + 1, INF, + X + Y);
		G.addedge(i, 2*N + 2, INF, - X + Y);
		G.addedge(i, 2*N + 3, INF, + X - Y);
		G.addedge(i, 2*N + 4, INF, - X - Y);
	}
	for(int i=N+1;i<=2*N;i++) {
		int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
		G.addedge(i, t, C, 0);
		G.addedge(2*N + 1, i, INF, - X - Y);
		G.addedge(2*N + 2, i, INF, + X - Y);
		G.addedge(2*N + 3, i, INF, - X + Y);
		G.addedge(2*N + 4, i, INF, + X + Y);
	}
	printf("%lld\n", -G.min_cost_max_flow(s, t));
}
```