#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;

#define Rep(i,l,r) for (int i = (l); i <= (r); ++ i)
#define RepD(i,r,l) for (int i = (r); i >= (l); -- i)
#define RepG(i,x) for (int i = hd[x]; i; i = e[i].nxt)
#define mkp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair <ll, ll> pll;

const int N = 2e4+5;
const ll inf = 1e15+7;

int n, cnt = 1, hd[N], vis[N], cur[N], S, T, qu[N*100];
ll d[N];
struct edge {int tt, nxt, c, f, w;} e[N<<1];

void addedge (int u, int v, int c, int w) {
	e[++ cnt] = (edge){v,hd[u],c,0,w}, hd[u] = cnt;
	e[++ cnt] = (edge){u,hd[v],0,0,-w}, hd[v] = cnt;
}

bool spfa () {
	int fr = 1, ta = 0;
	Rep(i,1,T) vis[i] = 0, d[i] = -inf, cur[i] = hd[i];
	d[S] = 0, qu[++ ta] = S, vis[S] = 1;
	while (fr<=ta) {
		int x = qu[fr ++]; vis[x] = 0;
		RepG(i,x) {
			int v = e[i].tt, cl = e[i].c-e[i].f;
			if (cl && d[v]<d[x]+e[i].w) {
				d[v] = d[x]+e[i].w;
				if (!vis[v]) vis[v] = 1, qu[++ ta] = v;
			}
		}
	}
	return d[T]>-inf;
}

ll dfs (int x, ll ff, ll &cst) {
	vis[x] = 1;
	if (x==T || !ff) return ff;
	ll res = 0;
	for (int &i = cur[x]; i; i = e[i].nxt) {
		int v = e[i].tt, cl = e[i].c-e[i].f;
		if (!vis[v] && cl && d[v]==d[x]+e[i].w) {
			ll fl = dfs (v, min (ff, 1ll*cl), cst);
			e[i].f += fl, e[i^1].f -= fl;
			res += fl, ff -= fl, cst += e[i].w*fl;
		}
		if (!ff) break;
	}
	return res;
}

ll mcfl () {
	ll cst = 0;
	while (spfa ()) dfs (S, inf, cst);
	return cst;
}

int main () {
	scanf ("%d", &n);
	S = 2*n+5, T = 2*n+6;
	Rep(i,1,n) {
		int x, y, c;
		scanf ("%d%d%d", &x, &y, &c);
		addedge (S, i, c, 0);
		addedge (i, 2*n+1, c, x+y);
		addedge (i, 2*n+2, c, x-y);
		addedge (i, 2*n+3, c, y-x);
		addedge (i, 2*n+4, c, -x-y);
	}
	Rep(i,1,n) {
		int x, y, c;
		scanf ("%d%d%d", &x, &y, &c);
		addedge (n+i, T, c, 0);
		addedge (2*n+1, n+i, c, -x-y);
		addedge (2*n+2, n+i, c, y-x);
		addedge (2*n+3, n+i, c, x-y);
		addedge (2*n+4, n+i, c, x+y);
	}
	printf ("%lld\n", mcfl ());
	return 0;
}
### Prompt

Please create a solution in Cpp to the following problem:

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;

#define Rep(i,l,r) for (int i = (l); i <= (r); ++ i)
#define RepD(i,r,l) for (int i = (r); i >= (l); -- i)
#define RepG(i,x) for (int i = hd[x]; i; i = e[i].nxt)
#define mkp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair <ll, ll> pll;

const int N = 2e4+5;
const ll inf = 1e15+7;

int n, cnt = 1, hd[N], vis[N], cur[N], S, T, qu[N*100];
ll d[N];
struct edge {int tt, nxt, c, f, w;} e[N<<1];

void addedge (int u, int v, int c, int w) {
	e[++ cnt] = (edge){v,hd[u],c,0,w}, hd[u] = cnt;
	e[++ cnt] = (edge){u,hd[v],0,0,-w}, hd[v] = cnt;
}

bool spfa () {
	int fr = 1, ta = 0;
	Rep(i,1,T) vis[i] = 0, d[i] = -inf, cur[i] = hd[i];
	d[S] = 0, qu[++ ta] = S, vis[S] = 1;
	while (fr<=ta) {
		int x = qu[fr ++]; vis[x] = 0;
		RepG(i,x) {
			int v = e[i].tt, cl = e[i].c-e[i].f;
			if (cl && d[v]<d[x]+e[i].w) {
				d[v] = d[x]+e[i].w;
				if (!vis[v]) vis[v] = 1, qu[++ ta] = v;
			}
		}
	}
	return d[T]>-inf;
}

ll dfs (int x, ll ff, ll &cst) {
	vis[x] = 1;
	if (x==T || !ff) return ff;
	ll res = 0;
	for (int &i = cur[x]; i; i = e[i].nxt) {
		int v = e[i].tt, cl = e[i].c-e[i].f;
		if (!vis[v] && cl && d[v]==d[x]+e[i].w) {
			ll fl = dfs (v, min (ff, 1ll*cl), cst);
			e[i].f += fl, e[i^1].f -= fl;
			res += fl, ff -= fl, cst += e[i].w*fl;
		}
		if (!ff) break;
	}
	return res;
}

ll mcfl () {
	ll cst = 0;
	while (spfa ()) dfs (S, inf, cst);
	return cst;
}

int main () {
	scanf ("%d", &n);
	S = 2*n+5, T = 2*n+6;
	Rep(i,1,n) {
		int x, y, c;
		scanf ("%d%d%d", &x, &y, &c);
		addedge (S, i, c, 0);
		addedge (i, 2*n+1, c, x+y);
		addedge (i, 2*n+2, c, x-y);
		addedge (i, 2*n+3, c, y-x);
		addedge (i, 2*n+4, c, -x-y);
	}
	Rep(i,1,n) {
		int x, y, c;
		scanf ("%d%d%d", &x, &y, &c);
		addedge (n+i, T, c, 0);
		addedge (2*n+1, n+i, c, -x-y);
		addedge (2*n+2, n+i, c, y-x);
		addedge (2*n+3, n+i, c, x-y);
		addedge (2*n+4, n+i, c, x+y);
	}
	printf ("%lld\n", mcfl ());
	return 0;
}
```