#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010,M=30005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int cnt,n,m,S,T;
ll cost;
int fir[N],siz;
struct edge{int v,w,fl,re;};
vector<edge> e[N];
void add(int u,int v,int w,int fl){
	e[u].push_back((edge){v,w,fl,(int)e[v].size()});
	e[v].push_back((edge){u,-w,0,(int)e[u].size()-1});
}
ll dist[N];
int dis[N];
vector<int> que;
bool inq[N];
bool spfa(){
	memset(dist,0xA0,8*(cnt+1));
	memset(inq,0,cnt+1);
	dist[S]=0;inq[S]=1;
	que.clear();que.push_back(S);
	for (unsigned i=0;i<que.size();i++){
		int x=que[i];
		for (auto cur : e[x])
		if (cur.fl&&(dist[cur.v]<dist[x]+cur.w)){
			if (!inq[cur.v]) {que.push_back(cur.v);inq[cur.v]=1;}
			dist[cur.v]=dist[x]+cur.w;
		}
		inq[x]=0;
	}
	return dist[T]>=0;
}
void bfs(){
	memset(dis,0x3f,4*(cnt+1));
	dis[S]=0;
	que.clear();que.push_back(S);
	for (unsigned i=0;i<que.size();i++){
		int x=que[i];
		for (auto cur : e[x])
		if ((dist[cur.v]==dist[x]+cur.w)&&cur.fl&&(dis[cur.v]>dis[x]+1)){
			que.push_back(cur.v);
			dis[cur.v]=dis[x]+1;
		}
	}
	return;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int fl=0,t=0;
	for (unsigned i=fir[x];i<e[x].size();i++){
		edge &cur=e[x][i];
		if ((dist[cur.v]==dist[x]+cur.w)&&cur.fl&&(dis[cur.v]>dis[x])){
			t=dfs(cur.v,min(flow-fl,cur.fl));
			fl+=t;cur.fl-=t;e[cur.v][cur.re].fl+=t;
			if (fl==flow) {fir[x]=i;return fl;}
		}
	}
	fir[x]=e[x].size();
	return fl;
}
int dinic(){
	int flow=0;
	while (spfa()){
		bfs();
		for (int i=0;i<=cnt;i++) fir[i]=0;
		int cur=dfs(S,inf);
		flow+=cur;
		cost+=(ll)dist[T]*cur;
	}
	return flow;
}
int main(){
	n=read();
	S=0;T=cnt=n*2+5;
	for (int i=1;i<=n;i++){
		int x=read(),y=read(),c=read();
		add(S,i,0,c);
		add(i,n*2+1,x+y,c);
		add(i,n*2+2,x-y,c);
		add(i,n*2+3,-x+y,c);
		add(i,n*2+4,-x-y,c);
	}
	for (int i=n+1;i<=n+n;i++){
		int x=read(),y=read(),c=read();
		add(i,T,0,c);
		add(n*2+1,i,-x-y,c);
		add(n*2+2,i,-x+y,c);
		add(n*2+3,i,x-y,c);
		add(n*2+4,i,x+y,c);
	}
	dinic();
	printf("%lld\n",cost);
	return 0;
}
### 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;
typedef long long ll;
const int N=2010,M=30005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int cnt,n,m,S,T;
ll cost;
int fir[N],siz;
struct edge{int v,w,fl,re;};
vector<edge> e[N];
void add(int u,int v,int w,int fl){
	e[u].push_back((edge){v,w,fl,(int)e[v].size()});
	e[v].push_back((edge){u,-w,0,(int)e[u].size()-1});
}
ll dist[N];
int dis[N];
vector<int> que;
bool inq[N];
bool spfa(){
	memset(dist,0xA0,8*(cnt+1));
	memset(inq,0,cnt+1);
	dist[S]=0;inq[S]=1;
	que.clear();que.push_back(S);
	for (unsigned i=0;i<que.size();i++){
		int x=que[i];
		for (auto cur : e[x])
		if (cur.fl&&(dist[cur.v]<dist[x]+cur.w)){
			if (!inq[cur.v]) {que.push_back(cur.v);inq[cur.v]=1;}
			dist[cur.v]=dist[x]+cur.w;
		}
		inq[x]=0;
	}
	return dist[T]>=0;
}
void bfs(){
	memset(dis,0x3f,4*(cnt+1));
	dis[S]=0;
	que.clear();que.push_back(S);
	for (unsigned i=0;i<que.size();i++){
		int x=que[i];
		for (auto cur : e[x])
		if ((dist[cur.v]==dist[x]+cur.w)&&cur.fl&&(dis[cur.v]>dis[x]+1)){
			que.push_back(cur.v);
			dis[cur.v]=dis[x]+1;
		}
	}
	return;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int fl=0,t=0;
	for (unsigned i=fir[x];i<e[x].size();i++){
		edge &cur=e[x][i];
		if ((dist[cur.v]==dist[x]+cur.w)&&cur.fl&&(dis[cur.v]>dis[x])){
			t=dfs(cur.v,min(flow-fl,cur.fl));
			fl+=t;cur.fl-=t;e[cur.v][cur.re].fl+=t;
			if (fl==flow) {fir[x]=i;return fl;}
		}
	}
	fir[x]=e[x].size();
	return fl;
}
int dinic(){
	int flow=0;
	while (spfa()){
		bfs();
		for (int i=0;i<=cnt;i++) fir[i]=0;
		int cur=dfs(S,inf);
		flow+=cur;
		cost+=(ll)dist[T]*cur;
	}
	return flow;
}
int main(){
	n=read();
	S=0;T=cnt=n*2+5;
	for (int i=1;i<=n;i++){
		int x=read(),y=read(),c=read();
		add(S,i,0,c);
		add(i,n*2+1,x+y,c);
		add(i,n*2+2,x-y,c);
		add(i,n*2+3,-x+y,c);
		add(i,n*2+4,-x-y,c);
	}
	for (int i=n+1;i<=n+n;i++){
		int x=read(),y=read(),c=read();
		add(i,T,0,c);
		add(n*2+1,i,-x-y,c);
		add(n*2+2,i,-x+y,c);
		add(n*2+3,i,x-y,c);
		add(n*2+4,i,x+y,c);
	}
	dinic();
	printf("%lld\n",cost);
	return 0;
}
```