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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(a>b)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

const int inf=LLONG_MAX/3;

//負辺あったら壊れるからBellman-Fordとかやるといいんじゃない？
template<class D>
struct mincf{
	using P=pair<D,int>;
	struct E{int to,rev,cap;D cost;};
	int n;
	vvc<E> g;
	vc<D> h,d;
	vi pv,pe;
	mincf(int nn):n(nn),g(n),h(n),d(n),pv(n),pe(n){}
	void ae(int a,int b,int cap,D cost){
		g[a].pb({b,(int)g[b].size(),cap,cost});
		g[b].pb({a,(int)g[a].size()-1,0,-cost});
	}
	P go(int s,int t,int f){
		priority_queue<P,vc<P>,greater<P>> q;
		fill(all(d),inf);
		d[s]=0;
		q.push(P(0,s));
		while(q.size()){
			D a;
			int v;
			tie(a,v)=q.top();q.pop();
			if(d[v]<a)continue;
			rep(i,(int)g[v].size()){
				E e=g[v][i];
				if(e.cap>0){
					D w=d[v]+e.cost+h[v]-h[e.to];
					if(w<d[e.to]){
						d[e.to]=w;
						q.push(P(w,e.to));
						pv[e.to]=v;
						pe[e.to]=i;
					}
				}
			}
		}
		if(d[t]==inf)return P(0,0);
		rep(i,n)
			h[i]+=d[i];
		int a=f;
		for(int v=t;v!=s;v=pv[v])
			chmin(a,g[pv[v]][pe[v]].cap);
		for(int v=t;v!=s;v=pv[v]){
			E& e=g[pv[v]][pe[v]];
			e.cap-=a;
			g[e.to][e.rev].cap+=a;
		}
		return P(a*h[t],a);
	}
	D calc(int s,int t,int f){
		D res=0;
		while(f>0){
			P w=go(s,t,f);
			if(w.b==0)
				return inf;
			f-=w.b;
			res+=w.a;
		}
		return res;
	}
};

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	
	int n;cin>>n;
	mincf<ll> mcf(1+n+4+n+1);
	
	const int V=2000000000;
	
	int m=0;
	rep(i,n){
		int x,y,c;cin>>x>>y>>c;
		mcf.ae(0,1+i,c,0);
		mcf.ae(1+i,1+n+0,c,V-(x+y));
		mcf.ae(1+i,1+n+1,c,V-(x-y));
		mcf.ae(1+i,1+n+2,c,V-(-x+y));
		mcf.ae(1+i,1+n+3,c,V-(-x-y));
		m+=c;
	}
	rep(i,n){
		int x,y,c;cin>>x>>y>>c;
		mcf.ae(1+n+4+i,1+n+4+n,c,0);
		mcf.ae(1+n+0,1+n+4+i,c,V-(-x-y));
		mcf.ae(1+n+1,1+n+4+i,c,V-(-x+y));
		mcf.ae(1+n+2,1+n+4+i,c,V-(x-y));
		mcf.ae(1+n+3,1+n+4+i,c,V-(x+y));
	}
	
	cout<<V*2*m-mcf.calc(0,1+n+4+n,m)<<endl;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(a>b)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

const int inf=LLONG_MAX/3;

//負辺あったら壊れるからBellman-Fordとかやるといいんじゃない？
template<class D>
struct mincf{
	using P=pair<D,int>;
	struct E{int to,rev,cap;D cost;};
	int n;
	vvc<E> g;
	vc<D> h,d;
	vi pv,pe;
	mincf(int nn):n(nn),g(n),h(n),d(n),pv(n),pe(n){}
	void ae(int a,int b,int cap,D cost){
		g[a].pb({b,(int)g[b].size(),cap,cost});
		g[b].pb({a,(int)g[a].size()-1,0,-cost});
	}
	P go(int s,int t,int f){
		priority_queue<P,vc<P>,greater<P>> q;
		fill(all(d),inf);
		d[s]=0;
		q.push(P(0,s));
		while(q.size()){
			D a;
			int v;
			tie(a,v)=q.top();q.pop();
			if(d[v]<a)continue;
			rep(i,(int)g[v].size()){
				E e=g[v][i];
				if(e.cap>0){
					D w=d[v]+e.cost+h[v]-h[e.to];
					if(w<d[e.to]){
						d[e.to]=w;
						q.push(P(w,e.to));
						pv[e.to]=v;
						pe[e.to]=i;
					}
				}
			}
		}
		if(d[t]==inf)return P(0,0);
		rep(i,n)
			h[i]+=d[i];
		int a=f;
		for(int v=t;v!=s;v=pv[v])
			chmin(a,g[pv[v]][pe[v]].cap);
		for(int v=t;v!=s;v=pv[v]){
			E& e=g[pv[v]][pe[v]];
			e.cap-=a;
			g[e.to][e.rev].cap+=a;
		}
		return P(a*h[t],a);
	}
	D calc(int s,int t,int f){
		D res=0;
		while(f>0){
			P w=go(s,t,f);
			if(w.b==0)
				return inf;
			f-=w.b;
			res+=w.a;
		}
		return res;
	}
};

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	
	int n;cin>>n;
	mincf<ll> mcf(1+n+4+n+1);
	
	const int V=2000000000;
	
	int m=0;
	rep(i,n){
		int x,y,c;cin>>x>>y>>c;
		mcf.ae(0,1+i,c,0);
		mcf.ae(1+i,1+n+0,c,V-(x+y));
		mcf.ae(1+i,1+n+1,c,V-(x-y));
		mcf.ae(1+i,1+n+2,c,V-(-x+y));
		mcf.ae(1+i,1+n+3,c,V-(-x-y));
		m+=c;
	}
	rep(i,n){
		int x,y,c;cin>>x>>y>>c;
		mcf.ae(1+n+4+i,1+n+4+n,c,0);
		mcf.ae(1+n+0,1+n+4+i,c,V-(-x-y));
		mcf.ae(1+n+1,1+n+4+i,c,V-(-x+y));
		mcf.ae(1+n+2,1+n+4+i,c,V-(x-y));
		mcf.ae(1+n+3,1+n+4+i,c,V-(x+y));
	}
	
	cout<<V*2*m-mcf.calc(0,1+n+4+n,m)<<endl;
}

```