#include <iostream>
#include <queue>

#define DEBUG() std::cerr << __FUNCTION__ << " " << __LINE__ << std::endl

using i64 = long long;

namespace flw {
	const int N = 2500 + 7, M = 400000 + 7;
	struct flow {
		int n, st, ed;
		i64 dis[N];
		int vis[N];
		struct edge {
			int to, nex, cap; i64 wei;
		} e[M];
		int fir[N], cur[N], eid = 1;

		void addedge(int u, int v, int c, i64 w) {
			e[++eid] = (edge){ v, fir[u], c, w }, fir[u] = eid;
		}
		void addflow(int u, int v, int c, i64 w) {
			addedge(u, v, c, w), addedge(v, u, 0, -w);
		}
		int bfs() {
			std::fill(vis + 1, vis + n + 1, 0);
			std::fill(dis + 1, dis + n + 1, 1ll << 60);
			std::copy(fir + 1, fir + n + 1, cur + 1);
			static std::queue<int> q;
			dis[ed] = 0, vis[ed] = 1, q.push(ed);
			for (int s; q.size(); ) {
				s = q.front(), q.pop();
				for (int i = fir[s]; i; i = e[i].nex)
					if (e[i ^ 1].cap && dis[e[i].to] > dis[s] - e[i].wei) {
						dis[e[i].to] = dis[s] - e[i].wei;
						if (!vis[e[i].to]) vis[e[i].to] = 1, q.push(e[i].to);
					}
				vis[s] = 0;
			}
			return dis[st] < 1ll << 60;
		}
		i64 dfs(int s, int f) {
			if (s == ed) return f;
			vis[s] = 1;
			int u = 0, t;
			for (int& i = cur[s]; i; i = e[i].nex) {
				if (!e[i].cap || vis[e[i].to] || dis[s] != dis[e[i].to] + e[i].wei) continue;
				t = dfs(e[i].to, std::min(e[i].cap, f - u));
				e[i].cap -= t, e[i ^ 1].cap += t, u += t;
				if (f == u) break;
			}
			return vis[s] = 0, u;
		}
		i64 dinic() {
			i64 mincost = 0;
			int f;
			while (bfs()) while (f = dfs(st, 1 << 28)) mincost += dis[st] * f;
			return mincost;
		}
	};
}

const int N = 2000 + 7;

int n;
flw::flow f;

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	f.st = 2 * n + 5, f.ed = f.n = f.st + 1;
	for (int i = 1, x, y, z; i <= n; ++i) {
		scanf("%d%d%d", &x, &y, &z),
		f.addflow(f.st, i, z, 0),
		f.addflow(i, 2 * n + 1, z, x + y),
		f.addflow(i, 2 * n + 2, z, x - y),
		f.addflow(i, 2 * n + 3, z, -x + y),
		f.addflow(i, 2 * n + 4, z, -x - y);
	}
	for (int i = n + 1, x, y, z; i <= 2 * n; ++i)
		scanf("%d%d%d", &x, &y, &z),
		f.addflow(i, f.ed, z, 0),
		f.addflow(2 * n + 1, i, z, -x - y),
		f.addflow(2 * n + 2, i, z, -x + y),
		f.addflow(2 * n + 3, i, z, x - y),
		f.addflow(2 * n + 4, i, z, x + y);
	printf("%lld\n", -f.dinic());

	return 0;
}

### Prompt

Please create a solution in CPP 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 <iostream>
#include <queue>

#define DEBUG() std::cerr << __FUNCTION__ << " " << __LINE__ << std::endl

using i64 = long long;

namespace flw {
	const int N = 2500 + 7, M = 400000 + 7;
	struct flow {
		int n, st, ed;
		i64 dis[N];
		int vis[N];
		struct edge {
			int to, nex, cap; i64 wei;
		} e[M];
		int fir[N], cur[N], eid = 1;

		void addedge(int u, int v, int c, i64 w) {
			e[++eid] = (edge){ v, fir[u], c, w }, fir[u] = eid;
		}
		void addflow(int u, int v, int c, i64 w) {
			addedge(u, v, c, w), addedge(v, u, 0, -w);
		}
		int bfs() {
			std::fill(vis + 1, vis + n + 1, 0);
			std::fill(dis + 1, dis + n + 1, 1ll << 60);
			std::copy(fir + 1, fir + n + 1, cur + 1);
			static std::queue<int> q;
			dis[ed] = 0, vis[ed] = 1, q.push(ed);
			for (int s; q.size(); ) {
				s = q.front(), q.pop();
				for (int i = fir[s]; i; i = e[i].nex)
					if (e[i ^ 1].cap && dis[e[i].to] > dis[s] - e[i].wei) {
						dis[e[i].to] = dis[s] - e[i].wei;
						if (!vis[e[i].to]) vis[e[i].to] = 1, q.push(e[i].to);
					}
				vis[s] = 0;
			}
			return dis[st] < 1ll << 60;
		}
		i64 dfs(int s, int f) {
			if (s == ed) return f;
			vis[s] = 1;
			int u = 0, t;
			for (int& i = cur[s]; i; i = e[i].nex) {
				if (!e[i].cap || vis[e[i].to] || dis[s] != dis[e[i].to] + e[i].wei) continue;
				t = dfs(e[i].to, std::min(e[i].cap, f - u));
				e[i].cap -= t, e[i ^ 1].cap += t, u += t;
				if (f == u) break;
			}
			return vis[s] = 0, u;
		}
		i64 dinic() {
			i64 mincost = 0;
			int f;
			while (bfs()) while (f = dfs(st, 1 << 28)) mincost += dis[st] * f;
			return mincost;
		}
	};
}

const int N = 2000 + 7;

int n;
flw::flow f;

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	f.st = 2 * n + 5, f.ed = f.n = f.st + 1;
	for (int i = 1, x, y, z; i <= n; ++i) {
		scanf("%d%d%d", &x, &y, &z),
		f.addflow(f.st, i, z, 0),
		f.addflow(i, 2 * n + 1, z, x + y),
		f.addflow(i, 2 * n + 2, z, x - y),
		f.addflow(i, 2 * n + 3, z, -x + y),
		f.addflow(i, 2 * n + 4, z, -x - y);
	}
	for (int i = n + 1, x, y, z; i <= 2 * n; ++i)
		scanf("%d%d%d", &x, &y, &z),
		f.addflow(i, f.ed, z, 0),
		f.addflow(2 * n + 1, i, z, -x - y),
		f.addflow(2 * n + 2, i, z, -x + y),
		f.addflow(2 * n + 3, i, z, x - y),
		f.addflow(2 * n + 4, i, z, x + y);
	printf("%lld\n", -f.dinic());

	return 0;
}

```