#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Maxn=2114;
struct edge{
	int to,rev;
	LL cap,cost;
	edge(int _to,int _cap,int _rev,int _cost){
		to=_to,cap=_cap,rev=_rev,cost=_cost;
	}
	edge(){
		;
	}
};
int src=2113,snk=2112;
vector<edge> G[Maxn];
int preve[Maxn],prevv[Maxn];
LL dist[Maxn];
int q[Maxn*Maxn],sq,eq,In[Maxn];
void add_edge(int u,int v,LL ca,LL co){
	G[u].pb(edge(v,ca,G[v].size(),co));
	G[v].pb(edge(u,0,G[u].size()-1,-co));
}
LL MCF(){
	LL ret=0;
	while (1){
		sq=eq=0;
		for (int i=0;i<Maxn;i++) dist[i]=1e18;
		dist[src]=0;
		q[eq++]=src;
		while (sq<eq){
			int x=q[sq++];In[x]=0;
			for (int i=0;i<G[x].size();i++){
				if (G[x][i].cap){
					int v=G[x][i].to;
					if (dist[v]>dist[x]+G[x][i].cost){
						dist[v]=dist[x]+G[x][i].cost;
						prevv[v]=x;preve[v]=i;
						if (!In[v]) q[eq++]=v,In[v]=1;
					}
				}
			}
		}
		if (dist[snk]==1e18){
			break;
		}
		LL fl=1e9;
		for (int i=snk;i!=src;i=prevv[i]){
			fl=min(fl,G[prevv[i]][preve[i]].cap);
		}
		ret+=1ll*fl*dist[snk];
		for (int i=snk;i!=src;i=prevv[i]){
			edge &E=G[prevv[i]][preve[i]];
			E.cap-=fl;
			G[i][E.rev].cap+=fl; 
		}
	}
	return ret;
}
int n;
int x[Maxn],y[Maxn],c[Maxn];
int _0=2020,_1=2021,_2=2022,_3=2023;
int __0=2010,__1=2011,__2=2012,__3=2013;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d %d %d",&x[i],&y[i],&c[i]);
		add_edge(src,i,c[i],0);
		add_edge(i,_0,c[i],-(x[i]+y[i]));
		add_edge(i,_1,c[i],-(x[i]-y[i]));
		add_edge(i,_2,c[i],-(y[i]-x[i]));
		add_edge(i,_3,c[i],-(-x[i]-y[i]));
	}
	for (int i=1;i<=n;i++){
		scanf("%d %d %d",&x[i],&y[i],&c[i]);
		add_edge(i+n,snk,c[i],0);
		add_edge(__0,i+n,c[i],-(x[i]+y[i]));
		add_edge(__1,i+n,c[i],-(x[i]-y[i]));
		add_edge(__2,i+n,c[i],-(y[i]-x[i]));
		add_edge(__3,i+n,c[i],-(-x[i]-y[i]));
	}
	add_edge(_0,__3,1e9,0);
	add_edge(_1,__2,1e9,0); 
	add_edge(_2,__1,1e9,0);
	add_edge(_3,__0,1e9,0);
	LL ans=MCF();
	printf("%lld\n",-ans);
	return 0;
}
### Prompt

Your task is to create 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<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Maxn=2114;
struct edge{
	int to,rev;
	LL cap,cost;
	edge(int _to,int _cap,int _rev,int _cost){
		to=_to,cap=_cap,rev=_rev,cost=_cost;
	}
	edge(){
		;
	}
};
int src=2113,snk=2112;
vector<edge> G[Maxn];
int preve[Maxn],prevv[Maxn];
LL dist[Maxn];
int q[Maxn*Maxn],sq,eq,In[Maxn];
void add_edge(int u,int v,LL ca,LL co){
	G[u].pb(edge(v,ca,G[v].size(),co));
	G[v].pb(edge(u,0,G[u].size()-1,-co));
}
LL MCF(){
	LL ret=0;
	while (1){
		sq=eq=0;
		for (int i=0;i<Maxn;i++) dist[i]=1e18;
		dist[src]=0;
		q[eq++]=src;
		while (sq<eq){
			int x=q[sq++];In[x]=0;
			for (int i=0;i<G[x].size();i++){
				if (G[x][i].cap){
					int v=G[x][i].to;
					if (dist[v]>dist[x]+G[x][i].cost){
						dist[v]=dist[x]+G[x][i].cost;
						prevv[v]=x;preve[v]=i;
						if (!In[v]) q[eq++]=v,In[v]=1;
					}
				}
			}
		}
		if (dist[snk]==1e18){
			break;
		}
		LL fl=1e9;
		for (int i=snk;i!=src;i=prevv[i]){
			fl=min(fl,G[prevv[i]][preve[i]].cap);
		}
		ret+=1ll*fl*dist[snk];
		for (int i=snk;i!=src;i=prevv[i]){
			edge &E=G[prevv[i]][preve[i]];
			E.cap-=fl;
			G[i][E.rev].cap+=fl; 
		}
	}
	return ret;
}
int n;
int x[Maxn],y[Maxn],c[Maxn];
int _0=2020,_1=2021,_2=2022,_3=2023;
int __0=2010,__1=2011,__2=2012,__3=2013;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d %d %d",&x[i],&y[i],&c[i]);
		add_edge(src,i,c[i],0);
		add_edge(i,_0,c[i],-(x[i]+y[i]));
		add_edge(i,_1,c[i],-(x[i]-y[i]));
		add_edge(i,_2,c[i],-(y[i]-x[i]));
		add_edge(i,_3,c[i],-(-x[i]-y[i]));
	}
	for (int i=1;i<=n;i++){
		scanf("%d %d %d",&x[i],&y[i],&c[i]);
		add_edge(i+n,snk,c[i],0);
		add_edge(__0,i+n,c[i],-(x[i]+y[i]));
		add_edge(__1,i+n,c[i],-(x[i]-y[i]));
		add_edge(__2,i+n,c[i],-(y[i]-x[i]));
		add_edge(__3,i+n,c[i],-(-x[i]-y[i]));
	}
	add_edge(_0,__3,1e9,0);
	add_edge(_1,__2,1e9,0); 
	add_edge(_2,__1,1e9,0);
	add_edge(_3,__0,1e9,0);
	LL ans=MCF();
	printf("%lld\n",-ans);
	return 0;
}
```