#include <bits/stdc++.h>

typedef long long ll;

namespace CF {
	#define ad(x) ((x - 1 ^ 1) + 1)

	const int N = 2054, M = 8000054;
	const ll INF = 0x3f3f3f3f3f3f3f3fll;

	struct edge {
		int u, v, c, f;
		edge (int u0 = 0, int v0 = 0, int c0 = 0, int f0 = 0): u(u0), v(v0), c(c0), f(f0) {}
	} e[M];

	int V, E, si = 1, ti = 2; ll flow, cost;
	int first[N], next[M];
	int cur[N], que[M << 1];
	ll dep[N];
	bool in_que[N], used[N];

	inline void addedge(int u, int v, int c, int f) {
		e[++E] = edge(u, v, c, f), next[E] = first[u], first[u] = E;
		e[++E] = edge(v, u, -c), next[E] = first[v], first[v] = E;
	}

	bool bfs() {
		int h = M, t = h + 1, i, x, y;
		memset(dep, 63, sizeof dep);
		que[h] = ti, dep[ti] = 0, in_que[ti] = true;
		for (; h < t; ) {
			x = que[h++], in_que[x] = false;
			for (i = first[x]; i; i = next[i])
				if (dep[y = e[i].v] > dep[x] - e[i].c && e[ad(i)].f) {
					dep[y] = dep[x] - e[i].c;
					if (!in_que[y])
						in_que[y] = true, (1 || dep[y] >= dep[que[h]] ? que[t++] : que[--h]) = y;
				}
		}
		return dep[si] < INF;
	}

	int dfs(int x, int lim) {
		int a, c, f = 0;
		if (x == ti || !lim) return lim;
		used[x] = true;
		for (int &i = cur[x]; i; i = next[i])
			if (dep[e[i].v] == dep[x] - e[i].c && e[i].f && !used[e[i].v]){
				a = std::min(lim - f, e[i].f);
				c = dfs(e[i].v, a);
				e[i].f -= c, e[ad(i)].f += c;
				if ((f += c) == lim) return f;
			}
		return f;
	}

	void Dinic() {
		int f;
		for (cost = flow = 0; bfs(); ) {
			memcpy(cur, first, sizeof cur);
			memset(used, 0, sizeof used);
			flow += f = dfs(si, INT_MAX);
			cost += dep[si] * f;
		}
	}
}

int main() {
	int i, n, w, x, y;
	scanf("%d", &n);
	for (i = 3; i < 3 + n; ++i) {
		scanf("%d%d%d", &x, &y, &w);
		CF::addedge(1, i, 0, w);
		CF::addedge(i, 3 + n * 2,  x + y, w);
		CF::addedge(i, 4 + n * 2,  x - y, w);
		CF::addedge(i, 5 + n * 2, -x + y, w);
		CF::addedge(i, 6 + n * 2, -x - y, w);
	}
	for (; i < 3 + n * 2; ++i) {
		scanf("%d%d%d", &x, &y, &w);
		CF::addedge(i, 2, 0, w);
		CF::addedge(3 + n * 2, i, -x - y, w);
		CF::addedge(4 + n * 2, i, -x + y, w);
		CF::addedge(5 + n * 2, i,  x - y, w);
		CF::addedge(6 + n * 2, i,  x + y, w);
	}
	CF::Dinic(), printf("%lld\n", -CF::cost);
	return 0;
}
### Prompt

Generate 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>

typedef long long ll;

namespace CF {
	#define ad(x) ((x - 1 ^ 1) + 1)

	const int N = 2054, M = 8000054;
	const ll INF = 0x3f3f3f3f3f3f3f3fll;

	struct edge {
		int u, v, c, f;
		edge (int u0 = 0, int v0 = 0, int c0 = 0, int f0 = 0): u(u0), v(v0), c(c0), f(f0) {}
	} e[M];

	int V, E, si = 1, ti = 2; ll flow, cost;
	int first[N], next[M];
	int cur[N], que[M << 1];
	ll dep[N];
	bool in_que[N], used[N];

	inline void addedge(int u, int v, int c, int f) {
		e[++E] = edge(u, v, c, f), next[E] = first[u], first[u] = E;
		e[++E] = edge(v, u, -c), next[E] = first[v], first[v] = E;
	}

	bool bfs() {
		int h = M, t = h + 1, i, x, y;
		memset(dep, 63, sizeof dep);
		que[h] = ti, dep[ti] = 0, in_que[ti] = true;
		for (; h < t; ) {
			x = que[h++], in_que[x] = false;
			for (i = first[x]; i; i = next[i])
				if (dep[y = e[i].v] > dep[x] - e[i].c && e[ad(i)].f) {
					dep[y] = dep[x] - e[i].c;
					if (!in_que[y])
						in_que[y] = true, (1 || dep[y] >= dep[que[h]] ? que[t++] : que[--h]) = y;
				}
		}
		return dep[si] < INF;
	}

	int dfs(int x, int lim) {
		int a, c, f = 0;
		if (x == ti || !lim) return lim;
		used[x] = true;
		for (int &i = cur[x]; i; i = next[i])
			if (dep[e[i].v] == dep[x] - e[i].c && e[i].f && !used[e[i].v]){
				a = std::min(lim - f, e[i].f);
				c = dfs(e[i].v, a);
				e[i].f -= c, e[ad(i)].f += c;
				if ((f += c) == lim) return f;
			}
		return f;
	}

	void Dinic() {
		int f;
		for (cost = flow = 0; bfs(); ) {
			memcpy(cur, first, sizeof cur);
			memset(used, 0, sizeof used);
			flow += f = dfs(si, INT_MAX);
			cost += dep[si] * f;
		}
	}
}

int main() {
	int i, n, w, x, y;
	scanf("%d", &n);
	for (i = 3; i < 3 + n; ++i) {
		scanf("%d%d%d", &x, &y, &w);
		CF::addedge(1, i, 0, w);
		CF::addedge(i, 3 + n * 2,  x + y, w);
		CF::addedge(i, 4 + n * 2,  x - y, w);
		CF::addedge(i, 5 + n * 2, -x + y, w);
		CF::addedge(i, 6 + n * 2, -x - y, w);
	}
	for (; i < 3 + n * 2; ++i) {
		scanf("%d%d%d", &x, &y, &w);
		CF::addedge(i, 2, 0, w);
		CF::addedge(3 + n * 2, i, -x - y, w);
		CF::addedge(4 + n * 2, i, -x + y, w);
		CF::addedge(5 + n * 2, i,  x - y, w);
		CF::addedge(6 + n * 2, i,  x + y, w);
	}
	CF::Dinic(), printf("%lld\n", -CF::cost);
	return 0;
}
```