#include <bits/stdc++.h>
using namespace std;

namespace TYC
{
	typedef long long ll;
	typedef pair<ll, int> pa;
	const int N = 2010, INF = 0x3f3f3f3f;
	const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;

	int n, S, T, Head[N], Pre[N], Vis[N];
	ll H[N], Dis[N];
	struct edge { int to, next, w, c; } E[N * 20];

	inline int read()
	{
		int x = 0, f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	void add(const int u, const int v, const int w, const int c)
	{
		static int ecnt = 1;
		E[++ecnt] = (edge){v, Head[u], w, c};
		Head[u] = ecnt;
		E[++ecnt] = (edge){u, Head[v], 0, -c};
		Head[v] = ecnt;
	}

	void spfa()
	{
		static queue<int> Q;
		Q.push(S);
		fill(H + 1, H + T + 1, -INFLL);
		H[S] = 0;
		while (!Q.empty())
		{
			int u = Q.front();
			Q.pop();
			Vis[u] = 0;
			for (int i = Head[u]; i; i = E[i].next)
			{
				int v = E[i].to;
				if (E[i].w && H[v] < H[u] + E[i].c)
				{
					H[v] = H[u] + E[i].c;
					if (!Vis[v])
						Q.push(v), Vis[v] = 1;
				}
			}
		}
	}

	bool Dijkstra()
	{
		static priority_queue<pa> Q;
		memset(Vis, 0, sizeof(int[T + 1]));
		fill(Dis + 1, Dis + T + 1, -INFLL);
		Q.push(pa(Dis[S] = 0, S));
		while (!Q.empty())
		{
			int u = Q.top().second; 
			Q.pop();
			if (Vis[u])
				continue;
			Vis[u] = 1;
			for (int i = Head[u]; i; i = E[i].next)
			{
				int v = E[i].to;
				ll w = E[i].c + H[u] - H[v];
				if (E[i].w && Dis[v] < Dis[u] + w)
				{
					Pre[v] = i;
					Dis[v] = Dis[u] + w;
					Q.push(pa(Dis[v], v));
				}
			}
		}
		return Dis[T] != -INFLL;
	}

	ll mcmf()
	{
		spfa();
		ll ans = 0;
		while (Dijkstra())
		{
			int flow = INF;
			for (int i = Pre[T]; i; i = Pre[E[i ^ 1].to])
				flow = min(flow, E[i].w);
			for (int i = Pre[T]; i; i = Pre[E[i ^ 1].to])
				E[i].w -= flow, E[i ^ 1].w += flow;
			ans += (ll)flow * (Dis[T] - H[S] + H[T]);
			for (int i = 1; i <= T; i++)
				H[i] += Dis[i];
		}
		return ans;
	}

	void work()
	{
		n = read();
		S = (n << 1) + 1, T = S + 5;
		for (int i = 1; i <= n; i++)
		{
			int x = read(), y = read();
			add(S, i, read(), 0);
			add(i, S + 1, INF, +x + y);
			add(i, S + 2, INF, +x - y);
			add(i, S + 3, INF, -x + y);
			add(i, S + 4, INF, -x - y);
		}
		for (int i = n + 1; i <= (n << 1); i++)
		{
			int x = read(), y = read();
			add(i, T, read(), 0);
			add(S + 1, i, INF, -x - y);
			add(S + 2, i, INF, -x + y);
			add(S + 3, i, INF, +x - y);
			add(S + 4, i, INF, +x + y);
		}
		printf("%lld\n", mcmf());
	}
}

int main()
{
	TYC::work();
	return 0;
}
### Prompt

Create a solution in CPP for 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>
using namespace std;

namespace TYC
{
	typedef long long ll;
	typedef pair<ll, int> pa;
	const int N = 2010, INF = 0x3f3f3f3f;
	const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;

	int n, S, T, Head[N], Pre[N], Vis[N];
	ll H[N], Dis[N];
	struct edge { int to, next, w, c; } E[N * 20];

	inline int read()
	{
		int x = 0, f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	void add(const int u, const int v, const int w, const int c)
	{
		static int ecnt = 1;
		E[++ecnt] = (edge){v, Head[u], w, c};
		Head[u] = ecnt;
		E[++ecnt] = (edge){u, Head[v], 0, -c};
		Head[v] = ecnt;
	}

	void spfa()
	{
		static queue<int> Q;
		Q.push(S);
		fill(H + 1, H + T + 1, -INFLL);
		H[S] = 0;
		while (!Q.empty())
		{
			int u = Q.front();
			Q.pop();
			Vis[u] = 0;
			for (int i = Head[u]; i; i = E[i].next)
			{
				int v = E[i].to;
				if (E[i].w && H[v] < H[u] + E[i].c)
				{
					H[v] = H[u] + E[i].c;
					if (!Vis[v])
						Q.push(v), Vis[v] = 1;
				}
			}
		}
	}

	bool Dijkstra()
	{
		static priority_queue<pa> Q;
		memset(Vis, 0, sizeof(int[T + 1]));
		fill(Dis + 1, Dis + T + 1, -INFLL);
		Q.push(pa(Dis[S] = 0, S));
		while (!Q.empty())
		{
			int u = Q.top().second; 
			Q.pop();
			if (Vis[u])
				continue;
			Vis[u] = 1;
			for (int i = Head[u]; i; i = E[i].next)
			{
				int v = E[i].to;
				ll w = E[i].c + H[u] - H[v];
				if (E[i].w && Dis[v] < Dis[u] + w)
				{
					Pre[v] = i;
					Dis[v] = Dis[u] + w;
					Q.push(pa(Dis[v], v));
				}
			}
		}
		return Dis[T] != -INFLL;
	}

	ll mcmf()
	{
		spfa();
		ll ans = 0;
		while (Dijkstra())
		{
			int flow = INF;
			for (int i = Pre[T]; i; i = Pre[E[i ^ 1].to])
				flow = min(flow, E[i].w);
			for (int i = Pre[T]; i; i = Pre[E[i ^ 1].to])
				E[i].w -= flow, E[i ^ 1].w += flow;
			ans += (ll)flow * (Dis[T] - H[S] + H[T]);
			for (int i = 1; i <= T; i++)
				H[i] += Dis[i];
		}
		return ans;
	}

	void work()
	{
		n = read();
		S = (n << 1) + 1, T = S + 5;
		for (int i = 1; i <= n; i++)
		{
			int x = read(), y = read();
			add(S, i, read(), 0);
			add(i, S + 1, INF, +x + y);
			add(i, S + 2, INF, +x - y);
			add(i, S + 3, INF, -x + y);
			add(i, S + 4, INF, -x - y);
		}
		for (int i = n + 1; i <= (n << 1); i++)
		{
			int x = read(), y = read();
			add(i, T, read(), 0);
			add(S + 1, i, INF, -x - y);
			add(S + 2, i, INF, -x + y);
			add(S + 3, i, INF, +x - y);
			add(S + 4, i, INF, +x + y);
		}
		printf("%lld\n", mcmf());
	}
}

int main()
{
	TYC::work();
	return 0;
}
```