#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<int>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define mem(a) memset((a),0,sizeof(a))
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}

const int N=2010,M=100005,inf=2e9+5;
int nedge=1,son[N],nextt[M],ed[M],cost[M],dist[N],di[M];
bool vis[N];
int last[N],que[N],laedge[N];
bool spfa(int s,int t,int n){
    for (int i=1;i<=n;i++) {dist[i]=-inf;last[i]=laedge[i]=vis[i]=que[i-1]=0;}
    int tot=1,l=0,r=0; que[0]=s; vis[s]=true; dist[s]=0;
    while (tot) {
        int k=que[l];
        vis[k]=false;
        if (++l==n) l=0;
        tot--; 
        for(int i=son[k];i;i=nextt[i]){
            if(di[i]>0&&dist[ed[i]]<(ll)dist[k]+cost[i]){
                dist[ed[i]]=dist[k]+cost[i]; laedge[ed[i]]=i; last[ed[i]]=k;
                if(vis[ed[i]]==0) {
                    if(++r==n)r=0;
                    que[r]=ed[i]; tot++; vis[ed[i]]=true;
                }
            }
        }
    }
    return last[t]>0;
}
ll costflow(int s,int t,int n){
	ll sum=0,cost=0;
    while(spfa(s,t,n)){
        int mmin=inf; 
        for(int i=t;last[i];i=last[i]){mmin=min(mmin,di[laedge[i]]);}
        sum+=mmin; 
        cost+=(ll)dist[t]*mmin; 
        for(int i=t;last[i];i=last[i]){
            di[laedge[i]]-=mmin;
            di[laedge[i]^1]+=mmin;
        }
    }
    return cost;
}
inline void aedge(int a,int b,int c,int d){
    nextt[++nedge]=son[a]; son[a]=nedge; ed[nedge]=b; di[nedge]=c; cost[nedge]=d;
}
inline void ins(int a,int b,int c,int d){
    aedge(a,b,c,d); aedge(b,a,0,-d);
    //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" fjzzq"<<endl;
}
const int X[4]={1,-1,1,-1},Y[4]={1,1,-1,-1};
int main(){
	int n=read(),s=2*n+5,t=2*n+6;
	For(i,1,n){
		int x=read(),y=read(),c=read();
		ins(s,i,c,0);
		For(j,0,3)ins(i,2*n+j+1,c,x*X[j]+y*Y[j]);
	}
	For(i,1,n){
		int x=read(),y=read(),c=read();
		ins(i+n,t,c,0);
		For(j,0,3)ins(2*n+j+1,i+n,c,-x*X[j]-y*Y[j]);
	}
	cout<<costflow(s,t,t)<<endl;
}
### Prompt

Generate 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 unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<int>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define mem(a) memset((a),0,sizeof(a))
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}

const int N=2010,M=100005,inf=2e9+5;
int nedge=1,son[N],nextt[M],ed[M],cost[M],dist[N],di[M];
bool vis[N];
int last[N],que[N],laedge[N];
bool spfa(int s,int t,int n){
    for (int i=1;i<=n;i++) {dist[i]=-inf;last[i]=laedge[i]=vis[i]=que[i-1]=0;}
    int tot=1,l=0,r=0; que[0]=s; vis[s]=true; dist[s]=0;
    while (tot) {
        int k=que[l];
        vis[k]=false;
        if (++l==n) l=0;
        tot--; 
        for(int i=son[k];i;i=nextt[i]){
            if(di[i]>0&&dist[ed[i]]<(ll)dist[k]+cost[i]){
                dist[ed[i]]=dist[k]+cost[i]; laedge[ed[i]]=i; last[ed[i]]=k;
                if(vis[ed[i]]==0) {
                    if(++r==n)r=0;
                    que[r]=ed[i]; tot++; vis[ed[i]]=true;
                }
            }
        }
    }
    return last[t]>0;
}
ll costflow(int s,int t,int n){
	ll sum=0,cost=0;
    while(spfa(s,t,n)){
        int mmin=inf; 
        for(int i=t;last[i];i=last[i]){mmin=min(mmin,di[laedge[i]]);}
        sum+=mmin; 
        cost+=(ll)dist[t]*mmin; 
        for(int i=t;last[i];i=last[i]){
            di[laedge[i]]-=mmin;
            di[laedge[i]^1]+=mmin;
        }
    }
    return cost;
}
inline void aedge(int a,int b,int c,int d){
    nextt[++nedge]=son[a]; son[a]=nedge; ed[nedge]=b; di[nedge]=c; cost[nedge]=d;
}
inline void ins(int a,int b,int c,int d){
    aedge(a,b,c,d); aedge(b,a,0,-d);
    //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" fjzzq"<<endl;
}
const int X[4]={1,-1,1,-1},Y[4]={1,1,-1,-1};
int main(){
	int n=read(),s=2*n+5,t=2*n+6;
	For(i,1,n){
		int x=read(),y=read(),c=read();
		ins(s,i,c,0);
		For(j,0,3)ins(i,2*n+j+1,c,x*X[j]+y*Y[j]);
	}
	For(i,1,n){
		int x=read(),y=read(),c=read();
		ins(i+n,t,c,0);
		For(j,0,3)ins(2*n+j+1,i+n,c,-x*X[j]-y*Y[j]);
	}
	cout<<costflow(s,t,t)<<endl;
}
```