#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=10100;
const int maxm=1000100;

int n,m,pre[maxn],jl[maxn],f[maxn],a[maxn],b[maxn];
int xa[maxn],xb[maxn],ya[maxn],yb[maxn],ca[maxn],cb[maxn];
int tot,nex[maxm*2],las[maxm*2],tov[maxm*2],flow[maxm*2],val[maxm*2];
long long dis[maxn],maxflow,mincost;
bool vis[maxn];
queue <int> q;

void qsort(int l,int r)
{
	int i=l;int j=r;
	int m=a[(i+j)/2];
	while (i<=j)
	{
		while (a[i]>m) i++;
		while (a[j]<m) j--;
		if (i<=j)
		{
			swap(a[i],a[j]);
			swap(b[i],b[j]);
			i++;j--;
		}
	}
	if (l<j) qsort(l,j);
	if (r>i) qsort(i,r); 
}

void insert(int x,int y,int ff,int vv)
{
	tot++;
	tov[tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
	flow[tot]=ff;
	val[tot]=vv;
	
	tot++;
	tov[tot]=x;
	nex[tot]=las[y];
	las[y]=tot;
	flow[tot]=0;
	val[tot]=-vv;
}

bool spfa(int s,int t)
{
	memset(dis,0x7f,sizeof(dis));
	memset(f,0x7f,sizeof(f));
	memset(vis,0,sizeof(vis));
	q.push(s); 
	vis[s]=1; 
	dis[s]=0; 
	pre[t]=-1;
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		vis[now]=0;
		for (int i=las[now];i;i=nex[i])
		{
			if (flow[i]>0 && dis[tov[i]]>dis[now]+val[i])
			{
				dis[tov[i]]=dis[now]+val[i];
				pre[tov[i]]=now;
				jl[tov[i]]=i;
				f[tov[i]]=min(f[now],flow[i]);
				if (!vis[tov[i]])
				{
					vis[tov[i]]=1;
					q.push(tov[i]);
				}
			}
		}
	}
	return pre[t]!=-1;
}

void MCMF()
{
	int t=2*n+6;
	while (spfa(1,t))
	{
		int now=t;
		maxflow+=f[t];
		mincost+=f[t]*dis[t];
		while (now!=1)
		{
			flow[jl[now]]-=f[t];
			flow[jl[now]^1]+=f[t];
			now=pre[now];
		}
	}
}

int main()
{
	tot=1;
	scanf("%d",&n);
	long long sum=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&xa[i],&ya[i],&ca[i]);
		sum+=ca[i];
		insert(1,i+1,ca[i],0);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&xb[i],&yb[i],&cb[i]);
		insert(i+1+n+4,2*n+6,cb[i],0);
	}
	for (int i=1;i<=n;i++)
	{
		insert(i+1,n+1+1,ca[i],10000+xa[i]+ya[i]);
		insert(i+1,n+1+2,ca[i],10000-xa[i]+ya[i]);
		insert(i+1,n+1+3,ca[i],10000+xa[i]-ya[i]);
		insert(i+1,n+1+4,ca[i],10000-xa[i]-ya[i]);
		
		insert(n+1+1,i+1+n+4,cb[i],10000-xb[i]-yb[i]);
		insert(n+1+2,i+1+n+4,cb[i],10000+xb[i]-yb[i]);
		insert(n+1+3,i+1+n+4,cb[i],10000-xb[i]+yb[i]);
		insert(n+1+4,i+1+n+4,cb[i],10000+xb[i]+yb[i]);
	}
	MCMF();
	sum=sum*20000;
	printf("%lld\n",sum-mincost);
}
### 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 <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=10100;
const int maxm=1000100;

int n,m,pre[maxn],jl[maxn],f[maxn],a[maxn],b[maxn];
int xa[maxn],xb[maxn],ya[maxn],yb[maxn],ca[maxn],cb[maxn];
int tot,nex[maxm*2],las[maxm*2],tov[maxm*2],flow[maxm*2],val[maxm*2];
long long dis[maxn],maxflow,mincost;
bool vis[maxn];
queue <int> q;

void qsort(int l,int r)
{
	int i=l;int j=r;
	int m=a[(i+j)/2];
	while (i<=j)
	{
		while (a[i]>m) i++;
		while (a[j]<m) j--;
		if (i<=j)
		{
			swap(a[i],a[j]);
			swap(b[i],b[j]);
			i++;j--;
		}
	}
	if (l<j) qsort(l,j);
	if (r>i) qsort(i,r); 
}

void insert(int x,int y,int ff,int vv)
{
	tot++;
	tov[tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
	flow[tot]=ff;
	val[tot]=vv;
	
	tot++;
	tov[tot]=x;
	nex[tot]=las[y];
	las[y]=tot;
	flow[tot]=0;
	val[tot]=-vv;
}

bool spfa(int s,int t)
{
	memset(dis,0x7f,sizeof(dis));
	memset(f,0x7f,sizeof(f));
	memset(vis,0,sizeof(vis));
	q.push(s); 
	vis[s]=1; 
	dis[s]=0; 
	pre[t]=-1;
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		vis[now]=0;
		for (int i=las[now];i;i=nex[i])
		{
			if (flow[i]>0 && dis[tov[i]]>dis[now]+val[i])
			{
				dis[tov[i]]=dis[now]+val[i];
				pre[tov[i]]=now;
				jl[tov[i]]=i;
				f[tov[i]]=min(f[now],flow[i]);
				if (!vis[tov[i]])
				{
					vis[tov[i]]=1;
					q.push(tov[i]);
				}
			}
		}
	}
	return pre[t]!=-1;
}

void MCMF()
{
	int t=2*n+6;
	while (spfa(1,t))
	{
		int now=t;
		maxflow+=f[t];
		mincost+=f[t]*dis[t];
		while (now!=1)
		{
			flow[jl[now]]-=f[t];
			flow[jl[now]^1]+=f[t];
			now=pre[now];
		}
	}
}

int main()
{
	tot=1;
	scanf("%d",&n);
	long long sum=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&xa[i],&ya[i],&ca[i]);
		sum+=ca[i];
		insert(1,i+1,ca[i],0);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&xb[i],&yb[i],&cb[i]);
		insert(i+1+n+4,2*n+6,cb[i],0);
	}
	for (int i=1;i<=n;i++)
	{
		insert(i+1,n+1+1,ca[i],10000+xa[i]+ya[i]);
		insert(i+1,n+1+2,ca[i],10000-xa[i]+ya[i]);
		insert(i+1,n+1+3,ca[i],10000+xa[i]-ya[i]);
		insert(i+1,n+1+4,ca[i],10000-xa[i]-ya[i]);
		
		insert(n+1+1,i+1+n+4,cb[i],10000-xb[i]-yb[i]);
		insert(n+1+2,i+1+n+4,cb[i],10000+xb[i]-yb[i]);
		insert(n+1+3,i+1+n+4,cb[i],10000-xb[i]+yb[i]);
		insert(n+1+4,i+1+n+4,cb[i],10000+xb[i]+yb[i]);
	}
	MCMF();
	sum=sum*20000;
	printf("%lld\n",sum-mincost);
}
```