#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define inf 2000000000
#define ll long long
//#define file
using namespace std;

int a[20011][4],ls[2011],g[2011],X[2001],Y[2001],c[2001],d[1000001],n,i,j,k,l,len,st,ed,h,t;
ll f[2011],ans;
bool bz[2011];

void NEW(int x,int y,int z,int w) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;a[len][2]=z;a[len][3]=w;}
void New(int x,int y,int z,int w) {NEW(x,y,z,w),NEW(y,x,0,-w);}

int main()
{
	#ifdef file
	freopen("agc034d.in","r",stdin);
	#endif
	
	scanf("%d",&n);st=n*2+1,ed=n*2+2;len=1;
	fo(i,1,n*2) scanf("%d%d%d",&X[i],&Y[i],&c[i]);
	fo(i,1,n) New(st,i,c[i],0),New(i,ed+1,c[i],X[i]+Y[i]),New(i,ed+2,c[i],X[i]-Y[i]),New(i,ed+3,c[i],-X[i]+Y[i]),New(i,ed+4,c[i],-X[i]-Y[i]);
	fo(i,n+1,n+n) New(i,ed,c[i],0),New(ed+1,i,c[i],-(X[i]+Y[i])),New(ed+2,i,c[i],-(X[i]-Y[i])),New(ed+3,i,c[i],-(-X[i]+Y[i])),New(ed+4,i,c[i],-(-X[i]-Y[i]));
	
	while (1)
	{
		memset(f,128,sizeof(f));
		h=0;t=1;
		d[1]=st;f[st]=0;bz[st]=1;
		while (h<t)
		{
			for (i=ls[d[++h]]; i; i=a[i][1])
			if (a[i][2] && f[d[h]]+a[i][3]>f[a[i][0]])
			{
				f[a[i][0]]=f[d[h]]+a[i][3],g[a[i][0]]=i;
				if (!bz[a[i][0]]) d[++t]=a[i][0],bz[a[i][0]]=1;
			}
			bz[d[h]]=0;
		}
		
		if (f[ed]<-1152921504606846976ll) break;
		l=inf;
		for (i=ed; i!=st; i=a[g[i]^1][0]) l=min(l,a[g[i]][2]);
		ans+=f[ed]*l;
		for (i=ed; i!=st; i=a[g[i]^1][0]) a[g[i]][2]-=l,a[g[i]^1][2]+=l;
	}
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	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 fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define inf 2000000000
#define ll long long
//#define file
using namespace std;

int a[20011][4],ls[2011],g[2011],X[2001],Y[2001],c[2001],d[1000001],n,i,j,k,l,len,st,ed,h,t;
ll f[2011],ans;
bool bz[2011];

void NEW(int x,int y,int z,int w) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;a[len][2]=z;a[len][3]=w;}
void New(int x,int y,int z,int w) {NEW(x,y,z,w),NEW(y,x,0,-w);}

int main()
{
	#ifdef file
	freopen("agc034d.in","r",stdin);
	#endif
	
	scanf("%d",&n);st=n*2+1,ed=n*2+2;len=1;
	fo(i,1,n*2) scanf("%d%d%d",&X[i],&Y[i],&c[i]);
	fo(i,1,n) New(st,i,c[i],0),New(i,ed+1,c[i],X[i]+Y[i]),New(i,ed+2,c[i],X[i]-Y[i]),New(i,ed+3,c[i],-X[i]+Y[i]),New(i,ed+4,c[i],-X[i]-Y[i]);
	fo(i,n+1,n+n) New(i,ed,c[i],0),New(ed+1,i,c[i],-(X[i]+Y[i])),New(ed+2,i,c[i],-(X[i]-Y[i])),New(ed+3,i,c[i],-(-X[i]+Y[i])),New(ed+4,i,c[i],-(-X[i]-Y[i]));
	
	while (1)
	{
		memset(f,128,sizeof(f));
		h=0;t=1;
		d[1]=st;f[st]=0;bz[st]=1;
		while (h<t)
		{
			for (i=ls[d[++h]]; i; i=a[i][1])
			if (a[i][2] && f[d[h]]+a[i][3]>f[a[i][0]])
			{
				f[a[i][0]]=f[d[h]]+a[i][3],g[a[i][0]]=i;
				if (!bz[a[i][0]]) d[++t]=a[i][0],bz[a[i][0]]=1;
			}
			bz[d[h]]=0;
		}
		
		if (f[ed]<-1152921504606846976ll) break;
		l=inf;
		for (i=ed; i!=st; i=a[g[i]^1][0]) l=min(l,a[g[i]][2]);
		ans+=f[ed]*l;
		for (i=ed; i!=st; i=a[g[i]^1][0]) a[g[i]][2]-=l,a[g[i]^1][2]+=l;
	}
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}
```