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

typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#define MN 3010
#define INF (1LL<<60)

//!!!!!!overflow
struct edge {
	int to, cap, rev;
	ll cost;
	edge(int to, int cap, ll cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};

int N;
vector<edge> g[MN];
ll h[MN], dst[MN];
int prevv[MN], preve[MN];

inline void add_edge(int f, int t, int cap, ll cost) {
	g[f].emplace_back(t, cap, cost, (int)g[t].size());
	g[t].emplace_back(f, 0, -cost, (int)g[f].size() - 1);
}

ll min_cost_flow(int s, int t, int f) {
	ll res = 0;
	memset(h, 0, sizeof(h));

	while (f > 0) {
		priority_queue<pii, vector<pii>, greater<pii> > que;
		fill(dst, dst + N + 1, INF);
		dst[s] = 0;
		que.push(mp(0, s));
		while (!que.empty()) {
			pii p = que.top(); que.pop();
			int v = p.se;
			if (dst[v] < p.fi) continue;
			rep(i, g[v].size()) {
				edge &e = g[v][i];
				ll nd = dst[v] + e.cost + h[v] - h[e.to];
				if (e.cap > 0 && dst[e.to] > nd) {
					dst[e.to] = nd;
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(mp(dst[e.to], e.to));
				}
			}
		}

		if (dst[t] == INF) return -1;
		rep(i, N) h[i] += dst[i];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, g[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}

	return res;
}

const int tx[4] = {1, 1, -1, -1};
const int ty[4] = {1, -1, 1, -1};

int main() {
	int n; cin >> n;

	int num = 0;
	int s = 0;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(s, i + 1, c, 0ll);
		rep(d, 4) {
			add_edge(i + 1, n + 1 + d, 1e9, x * tx[d] + y * ty[d]);
		}

		num += c;
	}

	int t = 1 + n + 4 + n;
	N = n * 2 + 6;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(1 + n + 4 + i, t, c, 0ll);
		rep(d, 4) {
			add_edge(n + 1 + d, 1 + n + 4 + i, 1e9, x * tx[3-d] + y * ty[3-d]);
		}		
	}

	ll ans = min_cost_flow(s, t, num);
	cout << -ans << endl;

	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;

typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#define MN 3010
#define INF (1LL<<60)

//!!!!!!overflow
struct edge {
	int to, cap, rev;
	ll cost;
	edge(int to, int cap, ll cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};

int N;
vector<edge> g[MN];
ll h[MN], dst[MN];
int prevv[MN], preve[MN];

inline void add_edge(int f, int t, int cap, ll cost) {
	g[f].emplace_back(t, cap, cost, (int)g[t].size());
	g[t].emplace_back(f, 0, -cost, (int)g[f].size() - 1);
}

ll min_cost_flow(int s, int t, int f) {
	ll res = 0;
	memset(h, 0, sizeof(h));

	while (f > 0) {
		priority_queue<pii, vector<pii>, greater<pii> > que;
		fill(dst, dst + N + 1, INF);
		dst[s] = 0;
		que.push(mp(0, s));
		while (!que.empty()) {
			pii p = que.top(); que.pop();
			int v = p.se;
			if (dst[v] < p.fi) continue;
			rep(i, g[v].size()) {
				edge &e = g[v][i];
				ll nd = dst[v] + e.cost + h[v] - h[e.to];
				if (e.cap > 0 && dst[e.to] > nd) {
					dst[e.to] = nd;
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(mp(dst[e.to], e.to));
				}
			}
		}

		if (dst[t] == INF) return -1;
		rep(i, N) h[i] += dst[i];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, g[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}

	return res;
}

const int tx[4] = {1, 1, -1, -1};
const int ty[4] = {1, -1, 1, -1};

int main() {
	int n; cin >> n;

	int num = 0;
	int s = 0;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(s, i + 1, c, 0ll);
		rep(d, 4) {
			add_edge(i + 1, n + 1 + d, 1e9, x * tx[d] + y * ty[d]);
		}

		num += c;
	}

	int t = 1 + n + 4 + n;
	N = n * 2 + 6;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(1 + n + 4 + i, t, c, 0ll);
		rep(d, 4) {
			add_edge(n + 1 + d, 1 + n + 4 + i, 1e9, x * tx[3-d] + y * ty[3-d]);
		}		
	}

	ll ans = min_cost_flow(s, t, num);
	cout << -ans << endl;

	return 0;
}
```