#include<cstdio>
#include<cstring>
#define fo(x,a,b) for(int x=(a),e_=(b);x<=e_;x++)
#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;
typedef long long ll;
const int N=50005;
struct node{int x,y,w;}a[N],b[N];
int go[N],nx[N],len[N],fee[N],hd[N],flow[N],q[N],pre[N];
ll dis[N],ans;
int n,tot,tl=1,mid1,mid2,mid3,mid4,S,T;
bool bz[N];

void In(int& a){
	a=0;char c=getchar();for(;c<48||c>57;c=getchar());
	for(;c>47&&c<58;c=getchar()) a=(a<<1)+(a<<3)+c-48;
}
void add(int u,int v,int w,int c){
	go[++tl]=v, nx[tl]=hd[u], hd[u]=tl; len[tl]=w, fee[tl]=c;
	go[++tl]=u, nx[tl]=hd[v], hd[v]=tl; len[tl]=0, fee[tl]=-c;
}
void init(){
	int u,v;
	In(n);
	fo(i,1,n) {
		In(u), In(v), In(a[i].w);
		a[i].x=u+v, a[i].y=u-v;
	}
	fo(i,1,n) {
		In(u), In(v), In(b[i].w);
		b[i].x=u+v, b[i].y=u-v;
	}

	mid1=n+1, mid2=n+2, mid3=n+3, mid4=n+4;
	S=n+4+n+1, T=S+1;
//	printf("S:%d T:%d mid1:%d mid2:%d mid3:%d mid4:%d\n",S,T,mid1,mid2,mid3,mid4);

	fo(i,1,n) {
		add(S, i, a[i].w, 0);
		add(mid4+i, T, b[i].w,0);
		
		add(i,mid1,a[i].w,a[i].x);
		add(i,mid2,a[i].w,-a[i].x);
		add(i,mid3,a[i].w,a[i].y);
		add(i,mid4,a[i].w,-a[i].y);

		add(mid1, mid4+i, b[i].w, -b[i].x);
		add(mid2, mid4+i, b[i].w, b[i].x);
		add(mid3, mid4+i, b[i].w, -b[i].y);
		add(mid4, mid4+i, b[i].w, b[i].y);
	}
}
bool spfa(){
	fo(i,1,T) dis[i]=-1e18, bz[i]=pre[i]=0; 
	dis[S]=0, flow[S]=1e9, pre[S]=0;
	int l=0, r=1, x; q[1]=S;
	while(l<r) {
		x=q[++l];
		for(int i=hd[x]; i; i=nx[i]) 
			if(len[i]>0 && dis[go[i]]<dis[x]+fee[i]) {
				dis[go[i]]=dis[x]+fee[i];
				flow[go[i]]=Min(flow[x],len[i]);
				pre[go[i]]=i^1;
				if(!bz[go[i]]) q[++r]=go[i], bz[go[i]]=true;
			}
		bz[x]=false;
	}
	return dis[T]>-1e18;
}
int main(){
	init();
	while(spfa()) {
		ans+=dis[T]*flow[T];
//		printf("got %lld\n",dis[T]*flow[T]);
		for(int x=T; x!=S; x=go[pre[x]]) 
			len[pre[x]]+=flow[T], len[pre[x]^1]-=flow[T];//, printf("-->%d\n",x);
	}
	printf("%lld",ans);
	return 0;
}

### Prompt

Your challenge is to write a cpp solution 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<cstdio>
#include<cstring>
#define fo(x,a,b) for(int x=(a),e_=(b);x<=e_;x++)
#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;
typedef long long ll;
const int N=50005;
struct node{int x,y,w;}a[N],b[N];
int go[N],nx[N],len[N],fee[N],hd[N],flow[N],q[N],pre[N];
ll dis[N],ans;
int n,tot,tl=1,mid1,mid2,mid3,mid4,S,T;
bool bz[N];

void In(int& a){
	a=0;char c=getchar();for(;c<48||c>57;c=getchar());
	for(;c>47&&c<58;c=getchar()) a=(a<<1)+(a<<3)+c-48;
}
void add(int u,int v,int w,int c){
	go[++tl]=v, nx[tl]=hd[u], hd[u]=tl; len[tl]=w, fee[tl]=c;
	go[++tl]=u, nx[tl]=hd[v], hd[v]=tl; len[tl]=0, fee[tl]=-c;
}
void init(){
	int u,v;
	In(n);
	fo(i,1,n) {
		In(u), In(v), In(a[i].w);
		a[i].x=u+v, a[i].y=u-v;
	}
	fo(i,1,n) {
		In(u), In(v), In(b[i].w);
		b[i].x=u+v, b[i].y=u-v;
	}

	mid1=n+1, mid2=n+2, mid3=n+3, mid4=n+4;
	S=n+4+n+1, T=S+1;
//	printf("S:%d T:%d mid1:%d mid2:%d mid3:%d mid4:%d\n",S,T,mid1,mid2,mid3,mid4);

	fo(i,1,n) {
		add(S, i, a[i].w, 0);
		add(mid4+i, T, b[i].w,0);
		
		add(i,mid1,a[i].w,a[i].x);
		add(i,mid2,a[i].w,-a[i].x);
		add(i,mid3,a[i].w,a[i].y);
		add(i,mid4,a[i].w,-a[i].y);

		add(mid1, mid4+i, b[i].w, -b[i].x);
		add(mid2, mid4+i, b[i].w, b[i].x);
		add(mid3, mid4+i, b[i].w, -b[i].y);
		add(mid4, mid4+i, b[i].w, b[i].y);
	}
}
bool spfa(){
	fo(i,1,T) dis[i]=-1e18, bz[i]=pre[i]=0; 
	dis[S]=0, flow[S]=1e9, pre[S]=0;
	int l=0, r=1, x; q[1]=S;
	while(l<r) {
		x=q[++l];
		for(int i=hd[x]; i; i=nx[i]) 
			if(len[i]>0 && dis[go[i]]<dis[x]+fee[i]) {
				dis[go[i]]=dis[x]+fee[i];
				flow[go[i]]=Min(flow[x],len[i]);
				pre[go[i]]=i^1;
				if(!bz[go[i]]) q[++r]=go[i], bz[go[i]]=true;
			}
		bz[x]=false;
	}
	return dis[T]>-1e18;
}
int main(){
	init();
	while(spfa()) {
		ans+=dis[T]*flow[T];
//		printf("got %lld\n",dis[T]*flow[T]);
		for(int x=T; x!=S; x=go[pre[x]]) 
			len[pre[x]]+=flow[T], len[pre[x]^1]-=flow[T];//, printf("-->%d\n",x);
	}
	printf("%lld",ans);
	return 0;
}

```