#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int n;

int s, t;

struct edge {
	int a, b, c, f;
	ll w;
};

const int N = 3000;

vector<edge> ed;
vector<int> eds[N];

void add_edge(int a, int b, int c, ll w) {
	edge x;
	x.a = a, x.b = b, x.c = c, x.f = 0, x.w = w;
	eds[a].push_back(ed.size());
	ed.push_back(x);
	swap(x.a, x.b), x.c = 0, x.w = -w;
	eds[b].push_back(ed.size());
	ed.push_back(x);
}

const ll INF = 1e18;

ll dd[N];
int go[N];
int en[N];

queue<int> qu;


ll flow() {
	ll ans = 0;
	while (true) {
		fill(dd, dd + t + 1, INF);
		fill(en, en + t + 1, 0);
		dd[s] = 0;
		qu.push(s);
		en[s] = 1;
		while (!qu.empty()) {
			int x = qu.front();
			qu.pop();
			en[x] = 0;
			for (int e: eds[x]) {
				if (ed[e].c == ed[e].f)
					continue;
				int u = ed[e].b;
				if (dd[u] > dd[x] + ed[e].w) {
					dd[u] = dd[x] + ed[e].w;
					go[u] = e;
					if (!en[u])
						en[u] = 1, qu.push(u);
				}
			}
		}
		if (dd[t] >= INF)
			break;
		int mn = 100;
		int now = t;
		while (now != s) {
			int e = go[now];
			mn = min(mn, ed[e].c - ed[e].f);
			now = ed[e].a;
		}
		ans += mn * dd[t];
		now = t;
		while (now != s) {
			int e = go[now];
			ed[e].f += mn;
			ed[e ^ 1].f -= mn;
			now = ed[e].a;
		}
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> n;
	s = 2 * n + 4;
	t = s + 1;
	for (int i = 0; i < n; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		add_edge(s, i, c, 0);
		add_edge(i, 2 * n, c, x + y);
		add_edge(i, 2 * n + 1, c, -x + y);
		add_edge(i, 2 * n + 2, c, x - y);
		add_edge(i, 2 * n + 3, c, -x - y);
	}
	for (int i = 0; i < n; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		add_edge(n + i, t, c, 0);
		add_edge(2 * n + 3, n + i, c, x + y);
		add_edge(2 * n + 2, n + i, c, -x + y);
		add_edge( 2 * n + 1, n + i, c, x - y);
		add_edge(2 * n + 0, n + i, c, -x - y);
	}
	cout << -flow() << "\n";
	return 0;
}



### Prompt

Your challenge is to write a cpp solution 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
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

int n;

int s, t;

struct edge {
	int a, b, c, f;
	ll w;
};

const int N = 3000;

vector<edge> ed;
vector<int> eds[N];

void add_edge(int a, int b, int c, ll w) {
	edge x;
	x.a = a, x.b = b, x.c = c, x.f = 0, x.w = w;
	eds[a].push_back(ed.size());
	ed.push_back(x);
	swap(x.a, x.b), x.c = 0, x.w = -w;
	eds[b].push_back(ed.size());
	ed.push_back(x);
}

const ll INF = 1e18;

ll dd[N];
int go[N];
int en[N];

queue<int> qu;


ll flow() {
	ll ans = 0;
	while (true) {
		fill(dd, dd + t + 1, INF);
		fill(en, en + t + 1, 0);
		dd[s] = 0;
		qu.push(s);
		en[s] = 1;
		while (!qu.empty()) {
			int x = qu.front();
			qu.pop();
			en[x] = 0;
			for (int e: eds[x]) {
				if (ed[e].c == ed[e].f)
					continue;
				int u = ed[e].b;
				if (dd[u] > dd[x] + ed[e].w) {
					dd[u] = dd[x] + ed[e].w;
					go[u] = e;
					if (!en[u])
						en[u] = 1, qu.push(u);
				}
			}
		}
		if (dd[t] >= INF)
			break;
		int mn = 100;
		int now = t;
		while (now != s) {
			int e = go[now];
			mn = min(mn, ed[e].c - ed[e].f);
			now = ed[e].a;
		}
		ans += mn * dd[t];
		now = t;
		while (now != s) {
			int e = go[now];
			ed[e].f += mn;
			ed[e ^ 1].f -= mn;
			now = ed[e].a;
		}
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> n;
	s = 2 * n + 4;
	t = s + 1;
	for (int i = 0; i < n; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		add_edge(s, i, c, 0);
		add_edge(i, 2 * n, c, x + y);
		add_edge(i, 2 * n + 1, c, -x + y);
		add_edge(i, 2 * n + 2, c, x - y);
		add_edge(i, 2 * n + 3, c, -x - y);
	}
	for (int i = 0; i < n; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		add_edge(n + i, t, c, 0);
		add_edge(2 * n + 3, n + i, c, x + y);
		add_edge(2 * n + 2, n + i, c, -x + y);
		add_edge( 2 * n + 1, n + i, c, x - y);
		add_edge(2 * n + 0, n + i, c, -x - y);
	}
	cout << -flow() << "\n";
	return 0;
}



```