#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 2019;
const int MAXM = 10005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, S, T, M1, M2, M3, M4;

struct Edge {
	int v, w, nxt;
	LL c;
} e[MAXM<<1];
int first[MAXN], eCnt;
	
inline void AddEdge(int u, int v, int w, LL c) {
	e[++eCnt].v = v;
	e[eCnt].w = w;
	e[eCnt].c = c;
	e[eCnt].nxt = first[u];
	first[u] = eCnt;
}

inline void Add(int u, int v, int w, LL c) {
	AddEdge(u, v, w, c);
	AddEdge(v, u, 0, -c);
}

LL dis[MAXN];
int inque[MAXN], pre[MAXN];
queue<int> q;

bool SPFA() {
	mset(dis, 0x80);
	dis[S] = 0;
	q.push(S);
	while (!q.empty()) {
		int u = q.front();
		q.pop(); inque[u] = 0;
		for (int i=first[u];i;i=e[i].nxt) {
			int v = e[i].v;
			if (e[i].w > 0 && dis[v] < dis[u] + e[i].c) {
				dis[v] = dis[u] + e[i].c;
				pre[v] = i;
				if (!inque[v]) {
					q.push(v);
					inque[v] = 1;
				}
			}
		}
	}
	return (dis[T] > 0);
}

LL Augment() {
	int flow = INF;
	for (int i=pre[T];i;i=pre[e[i^1].v]) {
		flow = min(flow, e[i].w);
	}
	for (int i=pre[T];i;i=pre[e[i^1].v]) {
		e[i].w -= flow;
		e[i^1].w += flow;
	}
	return dis[T] * flow;
}

void init() {
	read(n);
	S = n * 2 + 1; T = S + 1;
	M1 = T + 1; M2 = T + 2; M3 = T + 3; M4 = T + 4;
	eCnt = 1;
	for (int i=1;i<=n;++i) {
		int x, y, z;
		read(x); read(y); read(z);
		Add(S, i, z, 0);
		Add(i, M1, z, x + y);
		Add(i, M2, z, x - y);
		Add(i, M3, z, -x + y);
		Add(i, M4, z, -x - y);
	}
	for (int i=1;i<=n;++i) {
		int x, y, z;
		read(x); read(y); read(z);
		Add(n+i, T, z, 0);
		Add(M1, n+i, z, -x - y);
		Add(M2, n+i, z, -x + y);
		Add(M3, n+i, z, x - y);
		Add(M4, n+i, z, x + y);
	}
}

void solve() {
	LL ans = 0;
	while (SPFA()) {
		ans += Augment();
	}
	printf("%lld\n", ans);
}

int main() {
	init();
	solve();
	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
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 2019;
const int MAXM = 10005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, S, T, M1, M2, M3, M4;

struct Edge {
	int v, w, nxt;
	LL c;
} e[MAXM<<1];
int first[MAXN], eCnt;
	
inline void AddEdge(int u, int v, int w, LL c) {
	e[++eCnt].v = v;
	e[eCnt].w = w;
	e[eCnt].c = c;
	e[eCnt].nxt = first[u];
	first[u] = eCnt;
}

inline void Add(int u, int v, int w, LL c) {
	AddEdge(u, v, w, c);
	AddEdge(v, u, 0, -c);
}

LL dis[MAXN];
int inque[MAXN], pre[MAXN];
queue<int> q;

bool SPFA() {
	mset(dis, 0x80);
	dis[S] = 0;
	q.push(S);
	while (!q.empty()) {
		int u = q.front();
		q.pop(); inque[u] = 0;
		for (int i=first[u];i;i=e[i].nxt) {
			int v = e[i].v;
			if (e[i].w > 0 && dis[v] < dis[u] + e[i].c) {
				dis[v] = dis[u] + e[i].c;
				pre[v] = i;
				if (!inque[v]) {
					q.push(v);
					inque[v] = 1;
				}
			}
		}
	}
	return (dis[T] > 0);
}

LL Augment() {
	int flow = INF;
	for (int i=pre[T];i;i=pre[e[i^1].v]) {
		flow = min(flow, e[i].w);
	}
	for (int i=pre[T];i;i=pre[e[i^1].v]) {
		e[i].w -= flow;
		e[i^1].w += flow;
	}
	return dis[T] * flow;
}

void init() {
	read(n);
	S = n * 2 + 1; T = S + 1;
	M1 = T + 1; M2 = T + 2; M3 = T + 3; M4 = T + 4;
	eCnt = 1;
	for (int i=1;i<=n;++i) {
		int x, y, z;
		read(x); read(y); read(z);
		Add(S, i, z, 0);
		Add(i, M1, z, x + y);
		Add(i, M2, z, x - y);
		Add(i, M3, z, -x + y);
		Add(i, M4, z, -x - y);
	}
	for (int i=1;i<=n;++i) {
		int x, y, z;
		read(x); read(y); read(z);
		Add(n+i, T, z, 0);
		Add(M1, n+i, z, -x - y);
		Add(M2, n+i, z, -x + y);
		Add(M3, n+i, z, x - y);
		Add(M4, n+i, z, x + y);
	}
}

void solve() {
	LL ans = 0;
	while (SPFA()) {
		ans += Augment();
	}
	printf("%lld\n", ans);
}

int main() {
	init();
	solve();
	return 0;
}

```