#include<cstdio>
#include<algorithm>

const int MAX=1e9+7;
const long long MIN=-2e12-7;

void read_int (int &a) {
	char c=getchar(); a=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') a=(a<<1)+(a<<3)-48+c,c=getchar();
	return;
}

int n,num,S,T,c1,c2,c3,c4;

struct edge {
	int next,point,cost,size;
} r[200667]; int last[20037];

void link (int x,int y,int size,int cost) {
	static int tot=1;
	r[++tot]=(edge){last[x],y,cost,size}; last[x]=tot;
	r[++tot]=(edge){last[y],x,-cost,0}; last[y]=tot;
	return;
}

long long val[20003]; int flow[20003];
int pre[20003],cnt[20003];

int q[2000003];
bool bein[20003];

long long SPFA () {
	
	std::fill(val+1,val+num+1,MIN);
	val[S]=pre[S]=cnt[S]=0;
	flow[S]=MAX; flow[T]=0;
	
	int left,right,now;
	q[left=right=1]=S; bein[S]=true;
	
	while (left<=right) {
		now=q[left++]; bein[now]=false;
		for (int i=last[now];i;i=r[i].next)
			if (r[i].size&&val[now]+r[i].cost>val[r[i].point]) {
				val[r[i].point]=val[now]+r[i].cost;
				pre[r[i].point]=now,cnt[r[i].point]=i;
				flow[r[i].point]=r[i].size<flow[now]?r[i].size:flow[now];
				if (!bein[r[i].point])
					q[++right]=r[i].point,bein[r[i].point]=true;
			}
	}
	if (!flow[T]) return 0;
	now=T;
	while (pre[now]) {
		r[cnt[now]].size-=flow[T];
		r[cnt[now]^1].size+=flow[T];
		now=pre[now];
	}
	return val[T]*flow[T];
}

long long cost_flow () {
	long long ans=0,now;
	while ((now=SPFA())) ans+=now;
	return ans;
}

int main () {
	
	read_int(n);
	S=++num; T=++num;
	c1=++num; c2=++num; c3=++num; c4=++num;
	
	for (int i=1,rx,ry,rc;i<=n;i++) {
		read_int(rx); read_int(ry); read_int(rc);
		++num; link(S,num,rc,0);
		link(num,c1,MAX,rx+ry);
		link(num,c2,MAX,rx-ry);
		link(num,c3,MAX,-rx+ry);
		link(num,c4,MAX,-rx-ry);
	}
	
	for (int i=1,bx,by,bc;i<=n;i++) {
		read_int(bx); read_int(by); read_int(bc);
		++num; link(num,T,bc,0);
		link(c1,num,MAX,-bx-by);
		link(c2,num,MAX,-bx+by);
		link(c3,num,MAX,bx-by);
		link(c4,num,MAX,bx+by);
	}
	
	printf("%lld",cost_flow());
	
	return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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>

const int MAX=1e9+7;
const long long MIN=-2e12-7;

void read_int (int &a) {
	char c=getchar(); a=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') a=(a<<1)+(a<<3)-48+c,c=getchar();
	return;
}

int n,num,S,T,c1,c2,c3,c4;

struct edge {
	int next,point,cost,size;
} r[200667]; int last[20037];

void link (int x,int y,int size,int cost) {
	static int tot=1;
	r[++tot]=(edge){last[x],y,cost,size}; last[x]=tot;
	r[++tot]=(edge){last[y],x,-cost,0}; last[y]=tot;
	return;
}

long long val[20003]; int flow[20003];
int pre[20003],cnt[20003];

int q[2000003];
bool bein[20003];

long long SPFA () {
	
	std::fill(val+1,val+num+1,MIN);
	val[S]=pre[S]=cnt[S]=0;
	flow[S]=MAX; flow[T]=0;
	
	int left,right,now;
	q[left=right=1]=S; bein[S]=true;
	
	while (left<=right) {
		now=q[left++]; bein[now]=false;
		for (int i=last[now];i;i=r[i].next)
			if (r[i].size&&val[now]+r[i].cost>val[r[i].point]) {
				val[r[i].point]=val[now]+r[i].cost;
				pre[r[i].point]=now,cnt[r[i].point]=i;
				flow[r[i].point]=r[i].size<flow[now]?r[i].size:flow[now];
				if (!bein[r[i].point])
					q[++right]=r[i].point,bein[r[i].point]=true;
			}
	}
	if (!flow[T]) return 0;
	now=T;
	while (pre[now]) {
		r[cnt[now]].size-=flow[T];
		r[cnt[now]^1].size+=flow[T];
		now=pre[now];
	}
	return val[T]*flow[T];
}

long long cost_flow () {
	long long ans=0,now;
	while ((now=SPFA())) ans+=now;
	return ans;
}

int main () {
	
	read_int(n);
	S=++num; T=++num;
	c1=++num; c2=++num; c3=++num; c4=++num;
	
	for (int i=1,rx,ry,rc;i<=n;i++) {
		read_int(rx); read_int(ry); read_int(rc);
		++num; link(S,num,rc,0);
		link(num,c1,MAX,rx+ry);
		link(num,c2,MAX,rx-ry);
		link(num,c3,MAX,-rx+ry);
		link(num,c4,MAX,-rx-ry);
	}
	
	for (int i=1,bx,by,bc;i<=n;i++) {
		read_int(bx); read_int(by); read_int(bc);
		++num; link(num,T,bc,0);
		link(c1,num,MAX,-bx-by);
		link(c2,num,MAX,-bx+by);
		link(c3,num,MAX,bx-by);
		link(c4,num,MAX,bx+by);
	}
	
	printf("%lld",cost_flow());
	
	return 0;
}
```