#include <bits/stdc++.h>

using namespace std;

namespace jumpmelon
{
	typedef long long big;
	
	const int INF = 0x3f3f3f3f;
	const big INFLL = 0x3f3f3f3f3f3f3f3fLL;
	const int MAXN = 1000, MAXVC = (MAXN << 1) + 6, MAXEC = 10 * MAXN;
	struct edge { int v, f, c, next; } E[MAXEC << 1];
	bool Vis[MAXVC];
	int n, ec, vc, vs, vt, Head[MAXVC], Pre[MAXVC];
	big Dis[MAXVC], H[MAXVC];
	
	void add_edge(int u, int v, int f, int c)
	{
		E[ec] = (edge){v, f, c, Head[u]};
		Head[u] = ec++;
		E[ec] = (edge){u, 0, -c, Head[v]};
		Head[v] = ec++;
	}
	
	void SPFA()
	{
		queue<int> Q;
		fill(H, H + vc, -INFLL);
		H[vs] = 0;
		Q.push(vs);
		Vis[vs] = 1;
		while (!Q.empty())
		{
			int u = Q.front();
			Q.pop();
			Vis[u] = 0;
			for (int p = Head[u]; ~p; p = E[p].next)
				if (E[p].f && H[u] + E[p].c > H[E[p].v])
				{
					H[E[p].v] = H[u] + E[p].c;
					if (!Vis[E[p].v])
					{
						Q.push(E[p].v);
						Vis[E[p].v] = 1;
					}
				}
		}
	}
	
	bool Dijkstra()
	{
		typedef pair<big, int> pa;
		
		priority_queue<pa> Q;
		memset(Vis, 0, sizeof(bool[vc]));
		fill(Dis, Dis + vc, -INFLL);
		Q.push(pa(Dis[vs] = 0, vs));
		while (!Q.empty())
		{
			int u = Q.top().second;
			Q.pop();
			if (!Vis[u])
			{
				Vis[u] = 1;
				for (int p = Head[u]; ~p; p = E[p].next)
					if (E[p].f)
					{
						big w = H[u] + E[p].c - H[E[p].v];
						if (Dis[u] + w > Dis[E[p].v])
						{
							Pre[E[p].v] = p;
							Q.push(pa(Dis[E[p].v] = Dis[u] + w, E[p].v));
						}
					}
			}
		}
		return Dis[vt] > -INFLL;
	}
	
	big EK()
	{
		big ans = 0;
		SPFA();
		while (Dijkstra())
		{
			int f = INF;
			for (int x = vt; x != vs; x = E[Pre[x] ^ 1].v)
				if (E[Pre[x]].f < f)
					f = E[Pre[x]].f;
			for (int x = vt; x != vs; x = E[Pre[x] ^ 1].v)
			{
				E[Pre[x]].f -= f;
				E[Pre[x] ^ 1].f += f;
				ans += (big)f * E[Pre[x]].c;
			}
			for (int i = 0; i < vc; i++)
				H[i] += Dis[i];
		}
		return ans;
	}
	
	void work()
	{
		scanf("%d", &n);
		vc = (n << 1) + 6;
		vs = (n << 1);
		vt = (n << 1) + 1;
		memset(Head, -1, sizeof(int[vc]));
		for (int i = 0; i < n; i++)
		{
			int x, y, c;
			scanf("%d%d%d", &x, &y, &c);
			add_edge(vs, i, c, 0);
			add_edge(i, vt + 1, INF, +x + y);
			add_edge(i, vt + 2, INF, +x - y);
			add_edge(i, vt + 3, INF, -x + y);
			add_edge(i, vt + 4, INF, -x - y);
		}
		for (int i = n; i < (n << 1); i++)
		{
			int x, y, c;
			scanf("%d%d%d", &x, &y, &c);
			add_edge(vt + 1, i, INF, -x - y);
			add_edge(vt + 2, i, INF, -x + y);
			add_edge(vt + 3, i, INF, +x - y);
			add_edge(vt + 4, i, INF, +x + y);
			add_edge(i, vt, c, 0);
		}
		printf("%lld\n", EK());
	}
}

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

Construct a cpp code solution to the problem outlined:

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 jumpmelon
{
	typedef long long big;
	
	const int INF = 0x3f3f3f3f;
	const big INFLL = 0x3f3f3f3f3f3f3f3fLL;
	const int MAXN = 1000, MAXVC = (MAXN << 1) + 6, MAXEC = 10 * MAXN;
	struct edge { int v, f, c, next; } E[MAXEC << 1];
	bool Vis[MAXVC];
	int n, ec, vc, vs, vt, Head[MAXVC], Pre[MAXVC];
	big Dis[MAXVC], H[MAXVC];
	
	void add_edge(int u, int v, int f, int c)
	{
		E[ec] = (edge){v, f, c, Head[u]};
		Head[u] = ec++;
		E[ec] = (edge){u, 0, -c, Head[v]};
		Head[v] = ec++;
	}
	
	void SPFA()
	{
		queue<int> Q;
		fill(H, H + vc, -INFLL);
		H[vs] = 0;
		Q.push(vs);
		Vis[vs] = 1;
		while (!Q.empty())
		{
			int u = Q.front();
			Q.pop();
			Vis[u] = 0;
			for (int p = Head[u]; ~p; p = E[p].next)
				if (E[p].f && H[u] + E[p].c > H[E[p].v])
				{
					H[E[p].v] = H[u] + E[p].c;
					if (!Vis[E[p].v])
					{
						Q.push(E[p].v);
						Vis[E[p].v] = 1;
					}
				}
		}
	}
	
	bool Dijkstra()
	{
		typedef pair<big, int> pa;
		
		priority_queue<pa> Q;
		memset(Vis, 0, sizeof(bool[vc]));
		fill(Dis, Dis + vc, -INFLL);
		Q.push(pa(Dis[vs] = 0, vs));
		while (!Q.empty())
		{
			int u = Q.top().second;
			Q.pop();
			if (!Vis[u])
			{
				Vis[u] = 1;
				for (int p = Head[u]; ~p; p = E[p].next)
					if (E[p].f)
					{
						big w = H[u] + E[p].c - H[E[p].v];
						if (Dis[u] + w > Dis[E[p].v])
						{
							Pre[E[p].v] = p;
							Q.push(pa(Dis[E[p].v] = Dis[u] + w, E[p].v));
						}
					}
			}
		}
		return Dis[vt] > -INFLL;
	}
	
	big EK()
	{
		big ans = 0;
		SPFA();
		while (Dijkstra())
		{
			int f = INF;
			for (int x = vt; x != vs; x = E[Pre[x] ^ 1].v)
				if (E[Pre[x]].f < f)
					f = E[Pre[x]].f;
			for (int x = vt; x != vs; x = E[Pre[x] ^ 1].v)
			{
				E[Pre[x]].f -= f;
				E[Pre[x] ^ 1].f += f;
				ans += (big)f * E[Pre[x]].c;
			}
			for (int i = 0; i < vc; i++)
				H[i] += Dis[i];
		}
		return ans;
	}
	
	void work()
	{
		scanf("%d", &n);
		vc = (n << 1) + 6;
		vs = (n << 1);
		vt = (n << 1) + 1;
		memset(Head, -1, sizeof(int[vc]));
		for (int i = 0; i < n; i++)
		{
			int x, y, c;
			scanf("%d%d%d", &x, &y, &c);
			add_edge(vs, i, c, 0);
			add_edge(i, vt + 1, INF, +x + y);
			add_edge(i, vt + 2, INF, +x - y);
			add_edge(i, vt + 3, INF, -x + y);
			add_edge(i, vt + 4, INF, -x - y);
		}
		for (int i = n; i < (n << 1); i++)
		{
			int x, y, c;
			scanf("%d%d%d", &x, &y, &c);
			add_edge(vt + 1, i, INF, -x - y);
			add_edge(vt + 2, i, INF, -x + y);
			add_edge(vt + 3, i, INF, +x - y);
			add_edge(vt + 4, i, INF, +x + y);
			add_edge(i, vt, c, 0);
		}
		printf("%lld\n", EK());
	}
}

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