#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
#define int LL
using namespace std;
int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=1e5+10;
int nxt[M],head[M],cnt,w[M],c[M],to[M];
int pre[M],dis[M],edge[M],S,T,n;
bool in[M];
void add(int x,int y,int flow,int v){
	nxt[++cnt]=head[x]; head[x]=cnt; to[cnt]=y; c[cnt]=v; w[cnt]=flow;
}
void jb(int x,int y,int w,int v){
	add(x,y,w,v);
	add(y,x,0,-v);
}
bool spfa(){
	for (int i=S;i<=T;i++){
		dis[i]=-1e16;
		pre[i]=-1;
		edge[i]=0;
	}
	queue<int> q; q.push(S); in[S]=1; dis[S]=0;
	while (!q.empty()){
		int x=q.front(); q.pop(); in[x]=0;
		for (int i=head[x];~i;i=nxt[i]){
			int y=to[i];
			if (w[i] && dis[x]+c[i]>dis[y]){
				dis[y]=dis[x]+c[i];
				pre[y]=x;
				edge[y]=i;
				if (!in[y]) q.push(y),in[y]=1;
			}
		}
	}
	return pre[T]!=-1;
}
int cost,mx;
void maxflow(){
	int fl=1e9;
	for (int i=T;i!=S;i=pre[i]) fl=min(fl,w[edge[i]]);
	cost+=fl*dis[T]; mx+=fl;
	for (int i=T;i!=S;i=pre[i]) w[edge[i]]-=fl,w[edge[i]^1]+=fl;
}
signed main(){
	n=read(); S=0; T=2*n+5; cnt=-1; ms(head,-1);
	for (int i=1;i<=n;i++){
		int x=read(),y=read(),tt=read();
		jb(S,i,tt,0);
		jb(i,2*n+1,tt,x+y);
		jb(i,2*n+2,tt,x-y);
		jb(i,2*n+3,tt,-x+y);
		jb(i,2*n+4,tt,-x-y);
	}
	for (int i=n+1;i<=2*n;i++){
		int x=read(),y=read(),tt=read();
		jb(i,T,tt,0);
		jb(2*n+1,i,tt,-x-y);
		jb(2*n+2,i,tt,-x+y);
		jb(2*n+3,i,tt,x-y);
		jb(2*n+4,i,tt,x+y);
	}
	while (spfa()) maxflow();
	cout<<cost<<"\n";
	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<bits/stdc++.h>
#define LL long long
#define pb push_back
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
#define int LL
using namespace std;
int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=1e5+10;
int nxt[M],head[M],cnt,w[M],c[M],to[M];
int pre[M],dis[M],edge[M],S,T,n;
bool in[M];
void add(int x,int y,int flow,int v){
	nxt[++cnt]=head[x]; head[x]=cnt; to[cnt]=y; c[cnt]=v; w[cnt]=flow;
}
void jb(int x,int y,int w,int v){
	add(x,y,w,v);
	add(y,x,0,-v);
}
bool spfa(){
	for (int i=S;i<=T;i++){
		dis[i]=-1e16;
		pre[i]=-1;
		edge[i]=0;
	}
	queue<int> q; q.push(S); in[S]=1; dis[S]=0;
	while (!q.empty()){
		int x=q.front(); q.pop(); in[x]=0;
		for (int i=head[x];~i;i=nxt[i]){
			int y=to[i];
			if (w[i] && dis[x]+c[i]>dis[y]){
				dis[y]=dis[x]+c[i];
				pre[y]=x;
				edge[y]=i;
				if (!in[y]) q.push(y),in[y]=1;
			}
		}
	}
	return pre[T]!=-1;
}
int cost,mx;
void maxflow(){
	int fl=1e9;
	for (int i=T;i!=S;i=pre[i]) fl=min(fl,w[edge[i]]);
	cost+=fl*dis[T]; mx+=fl;
	for (int i=T;i!=S;i=pre[i]) w[edge[i]]-=fl,w[edge[i]^1]+=fl;
}
signed main(){
	n=read(); S=0; T=2*n+5; cnt=-1; ms(head,-1);
	for (int i=1;i<=n;i++){
		int x=read(),y=read(),tt=read();
		jb(S,i,tt,0);
		jb(i,2*n+1,tt,x+y);
		jb(i,2*n+2,tt,x-y);
		jb(i,2*n+3,tt,-x+y);
		jb(i,2*n+4,tt,-x-y);
	}
	for (int i=n+1;i<=2*n;i++){
		int x=read(),y=read(),tt=read();
		jb(i,T,tt,0);
		jb(2*n+1,i,tt,-x-y);
		jb(2*n+2,i,tt,-x+y);
		jb(2*n+3,i,tt,x-y);
		jb(2*n+4,i,tt,x+y);
	}
	while (spfa()) maxflow();
	cout<<cost<<"\n";
	return 0;
}


```