#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 DCXISSOHANDSOME
#define inf 2333333333333333333LL
#define inf1 2123333333

struct node { int t,v,op,next;ll c; }a[100010];

queue<int> q;

ll dis[2010],ans=0;
int x1[1010],y1[1010],c1[1010],x2[1010],y2[1010],c2[1010];
int head[2010],n,vs,vt,tot;
bool vis[2010],inq[2010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void add(int x,int y,int z,ll c)
{
	a[++tot].t=y;a[tot].v=z;a[tot].c=c;a[tot].op=tot+1;a[tot].next=head[x];head[x]=tot;
	a[++tot].t=x;a[tot].v=0;a[tot].c=-c;a[tot].op=tot-1;a[tot].next=head[y];head[y]=tot;
}

inline bool spfa()
{
	while (!q.empty()) q.pop();
	for (int i=vs;i<=vt;i++) dis[i]=-inf;
	memset(inq,false,sizeof(inq));
	dis[vt]=0;q.push(vt);inq[vt]=true;
	while (!q.empty())
	{
		int x=q.front();q.pop();
		for (int i=head[x];i;i=a[i].next) if (a[a[i].op].v)
		{
			int t=a[i].t;
			if (dis[t]<dis[x]-a[i].c)
			{
				dis[t]=dis[x]-a[i].c;
				if (!inq[t]) q.push(t),inq[t]=true;
			}
		}
		inq[x]=false;
	}
	return dis[vs]>-inf;
}

inline int dfs(int x,int y)
{
	if (x==vt||!y) return y;
	int res=0;vis[x]=true;
	for (int i=head[x];i;i=a[i].next)
	{
		int t=a[i].t;
		if (dis[t]!=dis[x]-a[i].c||vis[t]||!a[i].v) continue;
		int hh=dfs(t,min(y,a[i].v));
		if (!hh) continue;
		res+=hh;y-=hh;ans+=a[i].c*hh;
		a[i].v-=hh;a[a[i].op].v+=hh;
	}
	return res;
}

int main()
{
	n=rd();
	for (int i=1;i<=n;i++) x1[i]=rd(),y1[i]=rd(),c1[i]=rd();
	for (int i=1;i<=n;i++) x2[i]=rd(),y2[i]=rd(),c2[i]=rd();
	vs=0;vt=n*2+5;
	for (int i=1;i<=n;i++) add(vs,i,c1[i],0),add(n+i,vt,c2[i],0);
	for (int i=1;i<=n;i++)
	{
		add(i,n*2+1,inf1,x1[i]+y1[i]);
		add(i,n*2+2,inf1,x1[i]-y1[i]);
		add(i,n*2+3,inf1,-x1[i]+y1[i]);
		add(i,n*2+4,inf1,-x1[i]-y1[i]);
	}
	for (int i=1;i<=n;i++)
	{
		add(n*2+1,n+i,inf1,-x2[i]-y2[i]);
		add(n*2+2,n+i,inf1,-x2[i]+y2[i]);
		add(n*2+3,n+i,inf1,x2[i]-y2[i]);
		add(n*2+4,n+i,inf1,x2[i]+y2[i]);
	}
	while (spfa())
	{
		do
		{
			memset(vis,false,sizeof(vis));
			dfs(vs,inf1);
		}while (vis[vt]);
	}
	printf("%lld\n",ans);
	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>
using namespace std;
#define ll long long
#define y1 DCXISSOHANDSOME
#define inf 2333333333333333333LL
#define inf1 2123333333

struct node { int t,v,op,next;ll c; }a[100010];

queue<int> q;

ll dis[2010],ans=0;
int x1[1010],y1[1010],c1[1010],x2[1010],y2[1010],c2[1010];
int head[2010],n,vs,vt,tot;
bool vis[2010],inq[2010];

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline void add(int x,int y,int z,ll c)
{
	a[++tot].t=y;a[tot].v=z;a[tot].c=c;a[tot].op=tot+1;a[tot].next=head[x];head[x]=tot;
	a[++tot].t=x;a[tot].v=0;a[tot].c=-c;a[tot].op=tot-1;a[tot].next=head[y];head[y]=tot;
}

inline bool spfa()
{
	while (!q.empty()) q.pop();
	for (int i=vs;i<=vt;i++) dis[i]=-inf;
	memset(inq,false,sizeof(inq));
	dis[vt]=0;q.push(vt);inq[vt]=true;
	while (!q.empty())
	{
		int x=q.front();q.pop();
		for (int i=head[x];i;i=a[i].next) if (a[a[i].op].v)
		{
			int t=a[i].t;
			if (dis[t]<dis[x]-a[i].c)
			{
				dis[t]=dis[x]-a[i].c;
				if (!inq[t]) q.push(t),inq[t]=true;
			}
		}
		inq[x]=false;
	}
	return dis[vs]>-inf;
}

inline int dfs(int x,int y)
{
	if (x==vt||!y) return y;
	int res=0;vis[x]=true;
	for (int i=head[x];i;i=a[i].next)
	{
		int t=a[i].t;
		if (dis[t]!=dis[x]-a[i].c||vis[t]||!a[i].v) continue;
		int hh=dfs(t,min(y,a[i].v));
		if (!hh) continue;
		res+=hh;y-=hh;ans+=a[i].c*hh;
		a[i].v-=hh;a[a[i].op].v+=hh;
	}
	return res;
}

int main()
{
	n=rd();
	for (int i=1;i<=n;i++) x1[i]=rd(),y1[i]=rd(),c1[i]=rd();
	for (int i=1;i<=n;i++) x2[i]=rd(),y2[i]=rd(),c2[i]=rd();
	vs=0;vt=n*2+5;
	for (int i=1;i<=n;i++) add(vs,i,c1[i],0),add(n+i,vt,c2[i],0);
	for (int i=1;i<=n;i++)
	{
		add(i,n*2+1,inf1,x1[i]+y1[i]);
		add(i,n*2+2,inf1,x1[i]-y1[i]);
		add(i,n*2+3,inf1,-x1[i]+y1[i]);
		add(i,n*2+4,inf1,-x1[i]-y1[i]);
	}
	for (int i=1;i<=n;i++)
	{
		add(n*2+1,n+i,inf1,-x2[i]-y2[i]);
		add(n*2+2,n+i,inf1,-x2[i]+y2[i]);
		add(n*2+3,n+i,inf1,x2[i]-y2[i]);
		add(n*2+4,n+i,inf1,x2[i]+y2[i]);
	}
	while (spfa())
	{
		do
		{
			memset(vis,false,sizeof(vis));
			dfs(vs,inf1);
		}while (vis[vt]);
	}
	printf("%lld\n",ans);
	return 0;
}
```