/*
 　　　　　／＞　 フ
 　　　　　| 　_　 _|
 　 　　　／`ミ _x 彡
 　　 　 /　　　 　 |
 　　　 /　  ヽ　　 ?
 　／￣|　　 |　|　|
 　| (￣ヽ＿_ヽ_)_)
 　＼二つ
*/
  
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y, 0); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int N = 50500;
int vis[N], cnt, n, s, t;
int h[N], ne[N<<1], to[N<<1], w[N<<1]; ll dis[N], d[N<<1], tot = 1;
inline void add(int x, int y, int z, ll t) {
	ne[++tot] = h[x], to[h[x] = tot] = y, w[tot] = z, d[tot] = t;
}
inline void adde(int x, int y, int z, ll t) { add(x, y, z, t), add(y, x, 0, -t); }
const int inf = 0x3f3f3f3f;
queue<int> q;
bool spfa(void) {
	memset(dis, -0x3f, cnt * 8 + 30);
	memset(vis, 0, cnt * 4 + 30);
	q.push(s), dis[s] = 0;
	while (q.size()) {
		int x = q.front(); q.pop(); vis[x] = 0;
		for (int i = h[x]; i; i = ne[i]) {
			int y = to[i]; if (!w[i] || dis[y] >= dis[x] + d[i]) continue;
			dis[y] = dis[x] + d[i]; if (!vis[y]) vis[y] = 1, q.push(y);
		}
	}
	return dis[t] > -1e15;
}

int dfs(int x, int lim) {
	if (x == t || !lim) return lim;
	int res = 0, fl; vis[x] = 1;
	for (int i = h[x]; i; i = ne[i]) {
		int y = to[i]; if (vis[y]) continue;
		if (!w[i] || dis[y] != dis[x] + d[i]) continue;
		fl = dfs(y, min(w[i], lim));
		w[i] -= fl, w[i^1] += fl;
		res += fl, lim -= fl;
		if (!lim) return res;
	}
	return res;
}

int main() {
	read(n); cnt = 2 * n, s = ++cnt, t = ++cnt;
	int t1 = ++cnt, t2 = ++cnt, t3 = ++cnt, t4 = ++cnt;
	for (int i = 1, x, y, z;i <= n; i++) {
		read(x), read(y), read(z);
		adde(s, i, z, 0);
		adde(i, t1, inf, x + y);
		adde(i, t2, inf, x - y);
		adde(i, t3, inf, -x + y);
		adde(i, t4, inf, -x - y);
	}
	for (int i = 1, x, y, z; i <= n; i++) {
		read(x), read(y), read(z);
		adde(i + n, t, z, 0);
		adde(t1, i + n, inf, -x - y);
		adde(t2, i + n, inf, -x + y);
		adde(t3, i + n, inf, x - y);
		adde(t4, i + n, inf, x + y);
	}
	ll ans = 0;
	while (spfa()) 
		ans += dis[t] * dfs(s, inf);
	write(ans);
	return 0;
}
### Prompt

Please formulate 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
/*
 　　　　　／＞　 フ
 　　　　　| 　_　 _|
 　 　　　／`ミ _x 彡
 　　 　 /　　　 　 |
 　　　 /　  ヽ　　 ?
 　／￣|　　 |　|　|
 　| (￣ヽ＿_ヽ_)_)
 　＼二つ
*/
  
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y, 0); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int N = 50500;
int vis[N], cnt, n, s, t;
int h[N], ne[N<<1], to[N<<1], w[N<<1]; ll dis[N], d[N<<1], tot = 1;
inline void add(int x, int y, int z, ll t) {
	ne[++tot] = h[x], to[h[x] = tot] = y, w[tot] = z, d[tot] = t;
}
inline void adde(int x, int y, int z, ll t) { add(x, y, z, t), add(y, x, 0, -t); }
const int inf = 0x3f3f3f3f;
queue<int> q;
bool spfa(void) {
	memset(dis, -0x3f, cnt * 8 + 30);
	memset(vis, 0, cnt * 4 + 30);
	q.push(s), dis[s] = 0;
	while (q.size()) {
		int x = q.front(); q.pop(); vis[x] = 0;
		for (int i = h[x]; i; i = ne[i]) {
			int y = to[i]; if (!w[i] || dis[y] >= dis[x] + d[i]) continue;
			dis[y] = dis[x] + d[i]; if (!vis[y]) vis[y] = 1, q.push(y);
		}
	}
	return dis[t] > -1e15;
}

int dfs(int x, int lim) {
	if (x == t || !lim) return lim;
	int res = 0, fl; vis[x] = 1;
	for (int i = h[x]; i; i = ne[i]) {
		int y = to[i]; if (vis[y]) continue;
		if (!w[i] || dis[y] != dis[x] + d[i]) continue;
		fl = dfs(y, min(w[i], lim));
		w[i] -= fl, w[i^1] += fl;
		res += fl, lim -= fl;
		if (!lim) return res;
	}
	return res;
}

int main() {
	read(n); cnt = 2 * n, s = ++cnt, t = ++cnt;
	int t1 = ++cnt, t2 = ++cnt, t3 = ++cnt, t4 = ++cnt;
	for (int i = 1, x, y, z;i <= n; i++) {
		read(x), read(y), read(z);
		adde(s, i, z, 0);
		adde(i, t1, inf, x + y);
		adde(i, t2, inf, x - y);
		adde(i, t3, inf, -x + y);
		adde(i, t4, inf, -x - y);
	}
	for (int i = 1, x, y, z; i <= n; i++) {
		read(x), read(y), read(z);
		adde(i + n, t, z, 0);
		adde(t1, i + n, inf, -x - y);
		adde(t2, i + n, inf, -x + y);
		adde(t3, i + n, inf, x - y);
		adde(t4, i + n, inf, x + y);
	}
	ll ans = 0;
	while (spfa()) 
		ans += dis[t] * dfs(s, inf);
	write(ans);
	return 0;
}
```