#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL LMAX = 100;

LL ec = 1,to[2000005],cap[2000005],w[2000005],nxt[2000005],hed[1000005] = {0};
void add_edge(LL f,LL t,LL c,LL d){
	++ ec; to[ec] = t; cap[ec] = c; w[ec] = d; nxt[ec] = hed[f]; hed[f] = ec;
	++ ec; to[ec] = f; cap[ec] = 0; w[ec] = -d; nxt[ec] = hed[t]; hed[t] = ec;
}

LL dis[4005],inq[4005],flw[4005];
LL pre[4005],prv[4005];

queue <LL> q;
LL spfa(LL s,LL t){
	memset(dis,INF,sizeof(dis));
	memset(inq,0,sizeof(inq));
	memset(flw,0,sizeof(flw)); prv[t] = -1;
	q.push(s); inq[s] = 1; dis[s] = 0; flw[s] = INF;
	while(!q.empty()){
		LL u = q.front(); q.pop();
		inq[u] = 0;
		for(LL i = hed[u];i;i = nxt[i]){
			LL v = to[i];
			if(dis[v] > dis[u] + w[i] && cap[i]){
				dis[v] = dis[u] + w[i];
				prv[v] = u; pre[v] = i;
				flw[v] = min(flw[u],cap[i]);
				if(!inq[v]){
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return prv[t] != -1;
}

LL mxf = 0,mcf = 0;
void mcmf(LL s,LL t){
	while(spfa(s,t)){
		mxf += flw[t];
		mcf += flw[t] * dis[t];
		LL now = t;
		while(now != s){
			cap[pre[now]] -= flw[t];
			cap[pre[now] ^ 1] += flw[t];
			now = prv[now];
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	LL n,x,y,w,S,T;
	cin >> n;
	S = n + n + 5; T = S + 1;
	for(LL i = 1;i <= n;i ++){
		cin >> x >> y >> w;
		add_edge(S,i,w,0);
		add_edge(i,n + n + 1,INF,+ x + y);
		add_edge(i,n + n + 2,INF,+ x - y);
		add_edge(i,n + n + 3,INF,- x + y);
		add_edge(i,n + n + 4,INF,- x - y);
	}
	for(LL i = 1;i <= n;i ++){
		cin >> x >> y >> w;
		add_edge(i + n,T,w,0);
		add_edge(n + n + 1,i + n,INF,- x - y);
		add_edge(n + n + 2,i + n,INF,- x + y);
		add_edge(n + n + 3,i + n,INF,+ x - y);
		add_edge(n + n + 4,i + n,INF,+ x + y);
	}
	mcmf(S,T);
	cout << -mcf << endl;
	return 0;
}
//
### 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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL LMAX = 100;

LL ec = 1,to[2000005],cap[2000005],w[2000005],nxt[2000005],hed[1000005] = {0};
void add_edge(LL f,LL t,LL c,LL d){
	++ ec; to[ec] = t; cap[ec] = c; w[ec] = d; nxt[ec] = hed[f]; hed[f] = ec;
	++ ec; to[ec] = f; cap[ec] = 0; w[ec] = -d; nxt[ec] = hed[t]; hed[t] = ec;
}

LL dis[4005],inq[4005],flw[4005];
LL pre[4005],prv[4005];

queue <LL> q;
LL spfa(LL s,LL t){
	memset(dis,INF,sizeof(dis));
	memset(inq,0,sizeof(inq));
	memset(flw,0,sizeof(flw)); prv[t] = -1;
	q.push(s); inq[s] = 1; dis[s] = 0; flw[s] = INF;
	while(!q.empty()){
		LL u = q.front(); q.pop();
		inq[u] = 0;
		for(LL i = hed[u];i;i = nxt[i]){
			LL v = to[i];
			if(dis[v] > dis[u] + w[i] && cap[i]){
				dis[v] = dis[u] + w[i];
				prv[v] = u; pre[v] = i;
				flw[v] = min(flw[u],cap[i]);
				if(!inq[v]){
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return prv[t] != -1;
}

LL mxf = 0,mcf = 0;
void mcmf(LL s,LL t){
	while(spfa(s,t)){
		mxf += flw[t];
		mcf += flw[t] * dis[t];
		LL now = t;
		while(now != s){
			cap[pre[now]] -= flw[t];
			cap[pre[now] ^ 1] += flw[t];
			now = prv[now];
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	LL n,x,y,w,S,T;
	cin >> n;
	S = n + n + 5; T = S + 1;
	for(LL i = 1;i <= n;i ++){
		cin >> x >> y >> w;
		add_edge(S,i,w,0);
		add_edge(i,n + n + 1,INF,+ x + y);
		add_edge(i,n + n + 2,INF,+ x - y);
		add_edge(i,n + n + 3,INF,- x + y);
		add_edge(i,n + n + 4,INF,- x - y);
	}
	for(LL i = 1;i <= n;i ++){
		cin >> x >> y >> w;
		add_edge(i + n,T,w,0);
		add_edge(n + n + 1,i + n,INF,- x - y);
		add_edge(n + n + 2,i + n,INF,- x + y);
		add_edge(n + n + 3,i + n,INF,+ x - y);
		add_edge(n + n + 4,i + n,INF,+ x + y);
	}
	mcmf(S,T);
	cout << -mcf << endl;
	return 0;
}
//
```