#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=1e3+5,o[8]={6,7,4,5,2,3,0,1};
set<P>s[8],ss[8][8];
int n,i,j,k,l,x,y,c,tot,fl1[2][N][4],fl2[2][N];
ll f[8][8],w[2][N][4],ww[2][N][4][4],ans,d[8],mmx;
inline void calcf(){
	for(j=0;j<8;++j)for(k=0;k<8;++k)
		f[j][k]=j!=k && !ss[j][k].empty()?ss[j][k].rbegin()->first:-(1ll<<60);
}
vector<int>v1,v2;
int q[999],pre[8],t,www,u,ff[8];
bool inq[8];
inline void relax(int u,int v,ll ww){if(ww>d[v]){d[v]=ww;pre[v]=u;if(!inq[v])inq[v]=1,q[++www]=v;}}
inline void spfa(int S){
	if(s[S].empty())return;
	q[t=0,www=1]=S;memset(d,250,64);memset(inq,0,8);d[S]=0;
	for(;t<www;){
		u=q[++t];inq[u]=0;
		relax(u,o[u],d[u]);x=u>>2<<2;y=u&3;
		for(j=0;j<4;++j)if(j!=y)relax(u,x+j,(x?f[x+j][u]:f[u][x+j])+d[u]);
	}
	int mxid;ll mx=-(1ll<<60);
	for(j=4;j<8;++j)if(!s[j].empty() && s[j].rbegin()->first+s[S].rbegin()->first+d[j]>mx)
		mx=s[j].rbegin()->first+s[S].rbegin()->first+d[j],mxid=j;
	if(mx>mmx){
		mmx=mx;
		v2.clear();for(j=mxid;j!=S;j=pre[j])v2.push_back(j);v2.push_back(S);v1=v2;
	}
}
inline void del(int x){
	int o=x>>2,y=s[x].rbegin()->second;
	if(!--fl2[o][y])for(i=0;i<4;++i)s[o<<2|i].erase(P(w[o][y][i],y));
	if(1==++fl1[o][y][x&3])for(j=0;j<4;++j)
		if(j!=(x&3))ss[x][o<<2|j].insert(P(ww[o][y][x&3][j],y));
}
inline void mdy(int o,int x,int y){
	if(o)swap(x,y);
	int z=ss[x][y].rbegin()->second;
	if(0==--fl1[o][z][x&3])for(j=0;j<4;++j)if(j!=(x&3))ss[x][o<<2|j].erase(P(ww[o][z][x&3][j],z));
	if(1==++fl1[o][z][y&3])for(j=0;j<4;++j)if(j!=(y&3))ss[y][o<<2|j].insert(P(ww[o][z][y&3][j],z));
}
int main(){
	scanf("%d",&n);
	for(j=0;j<2;++j)for(i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&c);tot+=c*j;
		w[j][i][0]=x+y;w[j][i][1]=-x+y;w[j][i][2]=-x-y;w[j][i][3]=x-y;
		s[0+j*4].insert(P(w[j][i][0],i));s[1+j*4].insert(P(w[j][i][1],i));
		s[2+j*4].insert(P(w[j][i][2],i));s[3+j*4].insert(P(w[j][i][3],i));
		for(k=0;k<4;++k)for(l=0;l<4;++l)ww[j][i][k][l]=w[j][i][l]-w[j][i][k];
		fl2[j][i]=c;
	}
	for(;tot--;){
		mmx=-(1ll<<60);calcf();
		for(i=0;i<4;++i)spfa(i);
		ans+=mmx;reverse(v2.begin(),v2.end());
		del(v2[0]);del(v2.back());
		for(i=0;i+1<v2.size();++i)if((v2[i]&4)==(v2[i+1]&4))mdy(v2[i]>>2,v2[i],v2[i+1]);
			else ff[max(v2[i],v2[i+1])&3]+=v2[i]<v2[i+1]?1:-1;
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Your challenge is to write 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>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=1e3+5,o[8]={6,7,4,5,2,3,0,1};
set<P>s[8],ss[8][8];
int n,i,j,k,l,x,y,c,tot,fl1[2][N][4],fl2[2][N];
ll f[8][8],w[2][N][4],ww[2][N][4][4],ans,d[8],mmx;
inline void calcf(){
	for(j=0;j<8;++j)for(k=0;k<8;++k)
		f[j][k]=j!=k && !ss[j][k].empty()?ss[j][k].rbegin()->first:-(1ll<<60);
}
vector<int>v1,v2;
int q[999],pre[8],t,www,u,ff[8];
bool inq[8];
inline void relax(int u,int v,ll ww){if(ww>d[v]){d[v]=ww;pre[v]=u;if(!inq[v])inq[v]=1,q[++www]=v;}}
inline void spfa(int S){
	if(s[S].empty())return;
	q[t=0,www=1]=S;memset(d,250,64);memset(inq,0,8);d[S]=0;
	for(;t<www;){
		u=q[++t];inq[u]=0;
		relax(u,o[u],d[u]);x=u>>2<<2;y=u&3;
		for(j=0;j<4;++j)if(j!=y)relax(u,x+j,(x?f[x+j][u]:f[u][x+j])+d[u]);
	}
	int mxid;ll mx=-(1ll<<60);
	for(j=4;j<8;++j)if(!s[j].empty() && s[j].rbegin()->first+s[S].rbegin()->first+d[j]>mx)
		mx=s[j].rbegin()->first+s[S].rbegin()->first+d[j],mxid=j;
	if(mx>mmx){
		mmx=mx;
		v2.clear();for(j=mxid;j!=S;j=pre[j])v2.push_back(j);v2.push_back(S);v1=v2;
	}
}
inline void del(int x){
	int o=x>>2,y=s[x].rbegin()->second;
	if(!--fl2[o][y])for(i=0;i<4;++i)s[o<<2|i].erase(P(w[o][y][i],y));
	if(1==++fl1[o][y][x&3])for(j=0;j<4;++j)
		if(j!=(x&3))ss[x][o<<2|j].insert(P(ww[o][y][x&3][j],y));
}
inline void mdy(int o,int x,int y){
	if(o)swap(x,y);
	int z=ss[x][y].rbegin()->second;
	if(0==--fl1[o][z][x&3])for(j=0;j<4;++j)if(j!=(x&3))ss[x][o<<2|j].erase(P(ww[o][z][x&3][j],z));
	if(1==++fl1[o][z][y&3])for(j=0;j<4;++j)if(j!=(y&3))ss[y][o<<2|j].insert(P(ww[o][z][y&3][j],z));
}
int main(){
	scanf("%d",&n);
	for(j=0;j<2;++j)for(i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&c);tot+=c*j;
		w[j][i][0]=x+y;w[j][i][1]=-x+y;w[j][i][2]=-x-y;w[j][i][3]=x-y;
		s[0+j*4].insert(P(w[j][i][0],i));s[1+j*4].insert(P(w[j][i][1],i));
		s[2+j*4].insert(P(w[j][i][2],i));s[3+j*4].insert(P(w[j][i][3],i));
		for(k=0;k<4;++k)for(l=0;l<4;++l)ww[j][i][k][l]=w[j][i][l]-w[j][i][k];
		fl2[j][i]=c;
	}
	for(;tot--;){
		mmx=-(1ll<<60);calcf();
		for(i=0;i<4;++i)spfa(i);
		ans+=mmx;reverse(v2.begin(),v2.end());
		del(v2[0]);del(v2.back());
		for(i=0;i+1<v2.size();++i)if((v2[i]&4)==(v2[i+1]&4))mdy(v2[i]>>2,v2[i],v2[i+1]);
			else ff[max(v2[i],v2[i+1])&3]+=v2[i]<v2[i+1]?1:-1;
	}
	printf("%lld\n",ans);
	return 0;
}
```