#include<bits/stdc++.h>
using namespace std;

#define ll long long

namespace mincf{
	const int E=1e6;
	const int V=1e4;
	struct R{
		int to,nex;
		ll cost,flow;
	}r[E];
	int st,en,n,cnt,hea[V];
	
	void A(int u,int v,ll c,ll f){
		r[++cnt]=(R){v,hea[u],c,f}; hea[u]=cnt;
		r[++cnt]=(R){u,hea[v],-c,0};hea[v]=cnt;
	}
	void resta(int n_,int st_,int en_){
		memset(hea,0,sizeof hea);
		cnt=1;
		n=n_; st=st_; en=en_;
	}
	
	int pv[V],pe[V],in[V];
	queue<int>q;
	ll fl,f[V],d[V],ans,sf,inf;
	
	bool spfa(){
		while (!q.empty()) q.pop();
		memset(in,0,sizeof in);
		memset(d,62,sizeof d);
		f[st]=inf=d[0];
		d[st]=0;
		ll x,y,z;
		for (q.push(st);!q.empty();q.pop()){
			x=q.front(); in[x]=0;
			for (int i=hea[x];i>0;i=r[i].nex) if (r[i].flow){
				y=r[i].to;
				z=d[x]+r[i].cost;
				if (z<d[y]){
					d[y]=z;
					f[y]=min(f[x],r[i].flow);
					pv[y]=x;
					pe[y]=i;
					if (!in[y]){
						in[y]=1;
						q.push(y);
					}
				}
			}
		}
		return d[en]!=inf;
	}
	
	ll realmain(){
		sf=ans=0;
		while (spfa()){
			sf+=fl=f[en];
			ans+=fl*d[en];
			for (int x=en;x!=st;x=pv[x]){
				r[pe[x]].flow-=fl;
				r[pe[x]^1].flow+=fl;
			}
		}
		return ans;
	}
}


int n, s, t;

int main(){
    cin>>n;
    s=n*2+1; t=n*2+2;
    mincf::resta(t+6,s,t);
    for (int i=1;i<=n;++i){
        int x, y, c; cin>>x>>y>>c;
        mincf::A(s,i,0,c);
        for (int d=0;d<4;++d){
            ll v= (d&1? x: -x) + (d>>1&1? y: -y);
            mincf::A(i,t+1+d,v,c);
        }
    }
    for (int i=1;i<=n;++i){
        int x, y, c; cin>>x>>y>>c;
        mincf::A(i+n,t,0,c);
        for (int d=0;d<4;++d){
            ll v= (d&1? x: -x) + (d>>1&1? y: -y);
            mincf::A(t+1+d,i+n,-v,c);
        }
    }
    cout<<-mincf::realmain()<<endl;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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

namespace mincf{
	const int E=1e6;
	const int V=1e4;
	struct R{
		int to,nex;
		ll cost,flow;
	}r[E];
	int st,en,n,cnt,hea[V];
	
	void A(int u,int v,ll c,ll f){
		r[++cnt]=(R){v,hea[u],c,f}; hea[u]=cnt;
		r[++cnt]=(R){u,hea[v],-c,0};hea[v]=cnt;
	}
	void resta(int n_,int st_,int en_){
		memset(hea,0,sizeof hea);
		cnt=1;
		n=n_; st=st_; en=en_;
	}
	
	int pv[V],pe[V],in[V];
	queue<int>q;
	ll fl,f[V],d[V],ans,sf,inf;
	
	bool spfa(){
		while (!q.empty()) q.pop();
		memset(in,0,sizeof in);
		memset(d,62,sizeof d);
		f[st]=inf=d[0];
		d[st]=0;
		ll x,y,z;
		for (q.push(st);!q.empty();q.pop()){
			x=q.front(); in[x]=0;
			for (int i=hea[x];i>0;i=r[i].nex) if (r[i].flow){
				y=r[i].to;
				z=d[x]+r[i].cost;
				if (z<d[y]){
					d[y]=z;
					f[y]=min(f[x],r[i].flow);
					pv[y]=x;
					pe[y]=i;
					if (!in[y]){
						in[y]=1;
						q.push(y);
					}
				}
			}
		}
		return d[en]!=inf;
	}
	
	ll realmain(){
		sf=ans=0;
		while (spfa()){
			sf+=fl=f[en];
			ans+=fl*d[en];
			for (int x=en;x!=st;x=pv[x]){
				r[pe[x]].flow-=fl;
				r[pe[x]^1].flow+=fl;
			}
		}
		return ans;
	}
}


int n, s, t;

int main(){
    cin>>n;
    s=n*2+1; t=n*2+2;
    mincf::resta(t+6,s,t);
    for (int i=1;i<=n;++i){
        int x, y, c; cin>>x>>y>>c;
        mincf::A(s,i,0,c);
        for (int d=0;d<4;++d){
            ll v= (d&1? x: -x) + (d>>1&1? y: -y);
            mincf::A(i,t+1+d,v,c);
        }
    }
    for (int i=1;i<=n;++i){
        int x, y, c; cin>>x>>y>>c;
        mincf::A(i+n,t,0,c);
        for (int d=0;d<4;++d){
            ll v= (d&1? x: -x) + (d>>1&1? y: -y);
            mincf::A(t+1+d,i+n,-v,c);
        }
    }
    cout<<-mincf::realmain()<<endl;
}
```