#include<cstdio>
#include<cstring>
using namespace std;
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long
struct op{
	int go,ne,use;
	ll va;
};
const int N=1005;
int i,j,n,s,t,fa,fb,fc,fd,x,y,z,so,zja;
ll ans,ch;
int h[N*4],fr[N*4],dl[N*100],mp[N*4],f[N*4];
bool bz[N*4];
op lk[N*300];
int read()
{
	int x=0;char s=getchar();
	while ((s<'0')||(s>'9')) s=getchar();
	while ((s>='0')&&(s<='9')) x=x*10+(s-'0'),s=getchar();
	return x;
}
int min(int x,int y)
{
	if (x<y) return x;
	return y;
}
void ad(int x,int y,int us,int va)
{
	so++;lk[so].go=y;lk[so].ne=h[x];
	h[x]=so;lk[so].use=us;lk[so].va=va;
	so++;lk[so].go=x;lk[so].ne=h[y];
	h[y]=so;lk[so].use=0;lk[so].va=0-va;
}
bool bfs(int x)
{
	fo(i,1,fd) f[i]=-2000000000,fr[i]=0;
	mp[x]=10000;
	f[x]=0;int l,r,i;l=r=1;dl[l]=x;
	while (l<=r)
	{
		i=h[dl[l]];
		while (i)
		{
			if ((lk[i].use)&&(f[dl[l]]+lk[i].va>f[lk[i].go]))
			{
				f[lk[i].go]=lk[i].va+f[dl[l]];fr[lk[i].go]=i;
				mp[lk[i].go]=min(mp[dl[l]],lk[i].use);
				if (!bz[lk[i].go]){bz[lk[i].go]=true;r++;dl[r]=lk[i].go;}
			}
			i=lk[i].ne;
		}
		bz[dl[l]]=false;
		l++;
	}
	if (fr[t]) return true;
	return false;
}
int main()
{
	n=read();so=1;
	s=n*2+1;t=s+1;fa=t+1;fb=fa+1;fc=fb+1;fd=fc+1;
	fo(i,1,n)
	{
		x=read();y=read();z=read();
		ad(s,i,z,0);
		ad(i,fa,z,x+y);
		ad(i,fb,z,x-y);
		ad(i,fc,z,y-x);
		ad(i,fd,z,-x-y);
	}
	fo(i,n+1,n*2)
	{
		x=read();y=read();z=read();
		ad(i,t,z,0);
		ad(fa,i,z,-x-y);
		ad(fb,i,z,y-x);
		ad(fc,i,z,x-y);
		ad(fd,i,z,x+y);
	}
	while (bfs(s))
	{
		i=t;ch=mp[t];ans+=ch*f[t];
		while (i!=s)
		{
			lk[fr[i]].use-=mp[t];
			zja=fr[i]^1;
			lk[zja].use+=mp[t];
			i=lk[zja].go;
		}
	}
	printf("%lld\n",ans);
}

### Prompt

In CPP, your task is to solve 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>
using namespace std;
#define fo(i,a,b) for(i=a;i<=b;i++)
#define ll long long
struct op{
	int go,ne,use;
	ll va;
};
const int N=1005;
int i,j,n,s,t,fa,fb,fc,fd,x,y,z,so,zja;
ll ans,ch;
int h[N*4],fr[N*4],dl[N*100],mp[N*4],f[N*4];
bool bz[N*4];
op lk[N*300];
int read()
{
	int x=0;char s=getchar();
	while ((s<'0')||(s>'9')) s=getchar();
	while ((s>='0')&&(s<='9')) x=x*10+(s-'0'),s=getchar();
	return x;
}
int min(int x,int y)
{
	if (x<y) return x;
	return y;
}
void ad(int x,int y,int us,int va)
{
	so++;lk[so].go=y;lk[so].ne=h[x];
	h[x]=so;lk[so].use=us;lk[so].va=va;
	so++;lk[so].go=x;lk[so].ne=h[y];
	h[y]=so;lk[so].use=0;lk[so].va=0-va;
}
bool bfs(int x)
{
	fo(i,1,fd) f[i]=-2000000000,fr[i]=0;
	mp[x]=10000;
	f[x]=0;int l,r,i;l=r=1;dl[l]=x;
	while (l<=r)
	{
		i=h[dl[l]];
		while (i)
		{
			if ((lk[i].use)&&(f[dl[l]]+lk[i].va>f[lk[i].go]))
			{
				f[lk[i].go]=lk[i].va+f[dl[l]];fr[lk[i].go]=i;
				mp[lk[i].go]=min(mp[dl[l]],lk[i].use);
				if (!bz[lk[i].go]){bz[lk[i].go]=true;r++;dl[r]=lk[i].go;}
			}
			i=lk[i].ne;
		}
		bz[dl[l]]=false;
		l++;
	}
	if (fr[t]) return true;
	return false;
}
int main()
{
	n=read();so=1;
	s=n*2+1;t=s+1;fa=t+1;fb=fa+1;fc=fb+1;fd=fc+1;
	fo(i,1,n)
	{
		x=read();y=read();z=read();
		ad(s,i,z,0);
		ad(i,fa,z,x+y);
		ad(i,fb,z,x-y);
		ad(i,fc,z,y-x);
		ad(i,fd,z,-x-y);
	}
	fo(i,n+1,n*2)
	{
		x=read();y=read();z=read();
		ad(i,t,z,0);
		ad(fa,i,z,-x-y);
		ad(fb,i,z,y-x);
		ad(fc,i,z,x-y);
		ad(fd,i,z,x+y);
	}
	while (bfs(s))
	{
		i=t;ch=mp[t];ans+=ch*f[t];
		while (i!=s)
		{
			lk[fr[i]].use-=mp[t];
			zja=fr[i]^1;
			lk[zja].use+=mp[t];
			i=lk[zja].go;
		}
	}
	printf("%lld\n",ans);
}

```