//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 1011;
namespace Flow
{
	const int maxv = 2022;
	const int maxe = 20022;
	const ll inf = 1e18;
	int head[maxv], nxt[maxe], to[maxe], cap[maxe], cost[maxe], tot=1;
	void add_edge(int x, int y, int c, int w)
	{
		nxt[++tot] = head[x];
		head[x] = tot;
		to[tot] = y;
		cap[tot] = c;
		cost[tot] = w;
		swap(x, y);
		nxt[++tot] = head[x];
		head[x] = tot;
		to[tot] = y;
		cap[tot] = 0;
		cost[tot] = -w;
	}
	ll dis[maxv];
	bool inq[maxv];
	int q[maxv], qb, qe;
	void update()
	{
		if (qb==qe) return;
		int lst = qe-1;
		if (lst<0) lst = maxv-1;
		if (dis[q[qb]]>dis[q[lst]]) swap(q[qb], q[lst]);
	}
	void spfa(int S)
	{
		for (int i=0; i<maxv; i++) dis[i] = inf;
		qb = qe = 0;
		q[qe++] = S; inq[S] = true;
		dis[S] = 0;
		while (qb!=qe)
		{
			int x = q[qb++];
			inq[x] = false;
			if (qb>=maxv) qb = 0;
			update();
			for (int i=head[x]; i; i=nxt[i])
			{
				if (cap[i]&&dis[to[i]]>dis[x]+cost[i])
				{
					dis[to[i]] = dis[x]+cost[i];
					if (!inq[to[i]])
					{
						inq[to[i]] = true;
						q[qe++] = to[i];
						if (qe>=maxv) qe = 0;
						update();
					}
				}
			}
		}
	}
	bool vis[maxv];
	int dfs(int x, int T, int f)
	{
		if (x==T) return f;
		int of = f;
		vis[x] = true;
		for (int i=head[x]; i; i=nxt[i])
		{
			int u = to[i];
			if (!vis[u]&&cap[i]&&dis[u]==dis[x]+cost[i])
			{
				int d = dfs(u, T, min(f, cap[i]));
				cap[i] -= d;
				cap[i^1] += d;
				f -= d;
				if (!f) return of;
			}
		}
		return of-f;
	}
	ll min_cost_max_flow(int S, int T)
	{
		ll ret = 0;
		while (true)
		{
			spfa(S);
			if (dis[T]==inf) return ret;
			while (true)
			{
				memset(vis, 0, sizeof(vis));
				int f = dfs(S, T, 233333333);
				if (f==0) break;
				ret += 1ll*f*dis[T];
			}
		}
	}
}
int n;
pair<int,int> a[maxn], b[maxn];
int cnta[maxn], cntb[maxn];

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d%d%d", &a[i].FF, &a[i].SS, &cnta[i]); 
	for (int i=1; i<=n; i++) scanf("%d%d%d", &b[i].FF, &b[i].SS, &cntb[i]);
	int S = n+n+5, T = n+n+6;
    for (int i=1; i<=n; i++)
	{
		Flow::add_edge(S, i, cnta[i], 0);
		Flow::add_edge(n+i, T, cntb[i], 0);
		Flow::add_edge(i, n+n+1, 1e9, a[i].FF+a[i].SS);
		Flow::add_edge(n+n+1, n+i, 1e9, -b[i].FF-b[i].SS);
		Flow::add_edge(i, n+n+2, 1e9, a[i].FF-a[i].SS);
		Flow::add_edge(n+n+2, n+i, 1e9, -b[i].FF+b[i].SS);
		Flow::add_edge(i, n+n+3, 1e9, -a[i].FF+a[i].SS);
		Flow::add_edge(n+n+3, n+i, 1e9, b[i].FF-b[i].SS);
		Flow::add_edge(i, n+n+4, 1e9, -a[i].FF-a[i].SS);
		Flow::add_edge(n+n+4, n+i, 1e9, b[i].FF+b[i].SS);
	}
	cout<<-Flow::min_cost_max_flow(S, T)<<endl;
	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
//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 1011;
namespace Flow
{
	const int maxv = 2022;
	const int maxe = 20022;
	const ll inf = 1e18;
	int head[maxv], nxt[maxe], to[maxe], cap[maxe], cost[maxe], tot=1;
	void add_edge(int x, int y, int c, int w)
	{
		nxt[++tot] = head[x];
		head[x] = tot;
		to[tot] = y;
		cap[tot] = c;
		cost[tot] = w;
		swap(x, y);
		nxt[++tot] = head[x];
		head[x] = tot;
		to[tot] = y;
		cap[tot] = 0;
		cost[tot] = -w;
	}
	ll dis[maxv];
	bool inq[maxv];
	int q[maxv], qb, qe;
	void update()
	{
		if (qb==qe) return;
		int lst = qe-1;
		if (lst<0) lst = maxv-1;
		if (dis[q[qb]]>dis[q[lst]]) swap(q[qb], q[lst]);
	}
	void spfa(int S)
	{
		for (int i=0; i<maxv; i++) dis[i] = inf;
		qb = qe = 0;
		q[qe++] = S; inq[S] = true;
		dis[S] = 0;
		while (qb!=qe)
		{
			int x = q[qb++];
			inq[x] = false;
			if (qb>=maxv) qb = 0;
			update();
			for (int i=head[x]; i; i=nxt[i])
			{
				if (cap[i]&&dis[to[i]]>dis[x]+cost[i])
				{
					dis[to[i]] = dis[x]+cost[i];
					if (!inq[to[i]])
					{
						inq[to[i]] = true;
						q[qe++] = to[i];
						if (qe>=maxv) qe = 0;
						update();
					}
				}
			}
		}
	}
	bool vis[maxv];
	int dfs(int x, int T, int f)
	{
		if (x==T) return f;
		int of = f;
		vis[x] = true;
		for (int i=head[x]; i; i=nxt[i])
		{
			int u = to[i];
			if (!vis[u]&&cap[i]&&dis[u]==dis[x]+cost[i])
			{
				int d = dfs(u, T, min(f, cap[i]));
				cap[i] -= d;
				cap[i^1] += d;
				f -= d;
				if (!f) return of;
			}
		}
		return of-f;
	}
	ll min_cost_max_flow(int S, int T)
	{
		ll ret = 0;
		while (true)
		{
			spfa(S);
			if (dis[T]==inf) return ret;
			while (true)
			{
				memset(vis, 0, sizeof(vis));
				int f = dfs(S, T, 233333333);
				if (f==0) break;
				ret += 1ll*f*dis[T];
			}
		}
	}
}
int n;
pair<int,int> a[maxn], b[maxn];
int cnta[maxn], cntb[maxn];

int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d%d%d", &a[i].FF, &a[i].SS, &cnta[i]); 
	for (int i=1; i<=n; i++) scanf("%d%d%d", &b[i].FF, &b[i].SS, &cntb[i]);
	int S = n+n+5, T = n+n+6;
    for (int i=1; i<=n; i++)
	{
		Flow::add_edge(S, i, cnta[i], 0);
		Flow::add_edge(n+i, T, cntb[i], 0);
		Flow::add_edge(i, n+n+1, 1e9, a[i].FF+a[i].SS);
		Flow::add_edge(n+n+1, n+i, 1e9, -b[i].FF-b[i].SS);
		Flow::add_edge(i, n+n+2, 1e9, a[i].FF-a[i].SS);
		Flow::add_edge(n+n+2, n+i, 1e9, -b[i].FF+b[i].SS);
		Flow::add_edge(i, n+n+3, 1e9, -a[i].FF+a[i].SS);
		Flow::add_edge(n+n+3, n+i, 1e9, b[i].FF-b[i].SS);
		Flow::add_edge(i, n+n+4, 1e9, -a[i].FF-a[i].SS);
		Flow::add_edge(n+n+4, n+i, 1e9, b[i].FF+b[i].SS);
	}
	cout<<-Flow::min_cost_max_flow(S, T)<<endl;
	return 0;
}
```