#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <queue>
using namespace std;

namespace zyt
{
	template<typename T>
	inline bool read(T &x)
	{
		char c;
		bool f = false;
		x = 0;
		do
			c = getchar();
		while (c != EOF && c != '-' && !isdigit(c));
		if (c == EOF)
			return false;
		if (c == '-')
			f = true, c = getchar();
		do
			x = x * 10 + c - '0', c = getchar();
		while (isdigit(c));
		if (f)
			x = -x;
		return true;
	}
	template<typename T>
	inline void write(T x)
	{
		static char buf[20];
		char *pos = buf;
		if (x < 0)
			putchar('-'), x = -x;
		do
			*pos++ = x % 10 + '0';
		while (x /= 10);
		while (pos > buf)
			putchar(*--pos);
	}
	typedef long long ll;
	const int N = 1e3 + 10, P = N << 1, M = P * 5, INF = 0x3f3f3f3f;
	const ll LINF = 0x3f3f3f3f3f3f3f3fll;
	struct edge
	{
		int to, w, c, next;
	}e[M << 1];
	int n, s, t, p1, p2, p3, p4, head[P], ecnt;
	void add(const int a, const int b, const int c, const int d)
	{
		e[ecnt] = (edge){b, c, d, head[a]}, head[a] = ecnt++;
	}
	void addtw(const int a, const int b, const int c, const int d)
	{
		add(a, b, c, d), add(b, a, 0, -d);
	}
	namespace EK
	{
		int pre[P];
		ll dis[P];
		bool vis[P];
		bool SPFA()
		{
			static queue<int> q;
			memset(pre, -1, sizeof(int[t + 1]));
			memset(vis, 0, sizeof(bool[t + 1]));
			for (int i = 1; i <= t; i++)
				dis[i] = -LINF;
			q.push(s);
			dis[s] = 0;
			vis[s] = true;
			while (!q.empty())
			{
				int u = q.front();
				q.pop();
				vis[u] = false;
				for (int i = head[u]; ~i; i = e[i].next)
				{
					int v = e[i].to;
					if (e[i].w && dis[v] < dis[u] + e[i].c)
					{
						dis[v] = dis[u] + e[i].c, pre[v] = i;
						if (!vis[v])
							q.push(v), vis[v] = true;
					}
				}
			}
			return dis[t] > -LINF;
		}
		ll EK()
		{
			ll ans = 0;
			while (SPFA())
			{
				int i = pre[t], minn = INF;
				while (~i)
					minn = min(minn, e[i].w), i = pre[e[i ^ 1].to];
				i = pre[t];
				while (~i)
					e[i].w -= minn, e[i ^ 1].w += minn, i = pre[e[i ^ 1].to];
				ans += (ll)minn * dis[t];
			}
			return ans;
		}
	}
	int work()
	{
		read(n);
		p1 = (n << 1) + 1, p2 = p1 + 1, p3 = p2 + 1, p4 = p3 + 1, s = p4 + 1, t = s + 1;
		memset(head, -1, sizeof(int[t + 1]));
		for (int i = 1; i <= n; i++)
		{
			int x, y, c;
			read(x), read(y), read(c);
			addtw(i, p1, c, x + y);
			addtw(i, p2, c, x - y);
			addtw(i, p3, c, -x + y);
			addtw(i, p4, c, -x - y);
			addtw(s, i, c, 0);
		}
		for (int i = 1; i <= n; i++)
		{
			int x, y, c;
			read(x), read(y), read(c);
			addtw(p1, i + n, c, -x - y);
			addtw(p2, i + n, c, -x + y);
			addtw(p3, i + n, c, x - y);
			addtw(p4, i + n, c, x + y);
			addtw(i + n, t, c, 0);
		}
		write(EK::EK());
		return 0;
	}
}
int main()
{
	return zyt::work();
}
### Prompt

Develop a solution in CPP to the problem described below:

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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <queue>
using namespace std;

namespace zyt
{
	template<typename T>
	inline bool read(T &x)
	{
		char c;
		bool f = false;
		x = 0;
		do
			c = getchar();
		while (c != EOF && c != '-' && !isdigit(c));
		if (c == EOF)
			return false;
		if (c == '-')
			f = true, c = getchar();
		do
			x = x * 10 + c - '0', c = getchar();
		while (isdigit(c));
		if (f)
			x = -x;
		return true;
	}
	template<typename T>
	inline void write(T x)
	{
		static char buf[20];
		char *pos = buf;
		if (x < 0)
			putchar('-'), x = -x;
		do
			*pos++ = x % 10 + '0';
		while (x /= 10);
		while (pos > buf)
			putchar(*--pos);
	}
	typedef long long ll;
	const int N = 1e3 + 10, P = N << 1, M = P * 5, INF = 0x3f3f3f3f;
	const ll LINF = 0x3f3f3f3f3f3f3f3fll;
	struct edge
	{
		int to, w, c, next;
	}e[M << 1];
	int n, s, t, p1, p2, p3, p4, head[P], ecnt;
	void add(const int a, const int b, const int c, const int d)
	{
		e[ecnt] = (edge){b, c, d, head[a]}, head[a] = ecnt++;
	}
	void addtw(const int a, const int b, const int c, const int d)
	{
		add(a, b, c, d), add(b, a, 0, -d);
	}
	namespace EK
	{
		int pre[P];
		ll dis[P];
		bool vis[P];
		bool SPFA()
		{
			static queue<int> q;
			memset(pre, -1, sizeof(int[t + 1]));
			memset(vis, 0, sizeof(bool[t + 1]));
			for (int i = 1; i <= t; i++)
				dis[i] = -LINF;
			q.push(s);
			dis[s] = 0;
			vis[s] = true;
			while (!q.empty())
			{
				int u = q.front();
				q.pop();
				vis[u] = false;
				for (int i = head[u]; ~i; i = e[i].next)
				{
					int v = e[i].to;
					if (e[i].w && dis[v] < dis[u] + e[i].c)
					{
						dis[v] = dis[u] + e[i].c, pre[v] = i;
						if (!vis[v])
							q.push(v), vis[v] = true;
					}
				}
			}
			return dis[t] > -LINF;
		}
		ll EK()
		{
			ll ans = 0;
			while (SPFA())
			{
				int i = pre[t], minn = INF;
				while (~i)
					minn = min(minn, e[i].w), i = pre[e[i ^ 1].to];
				i = pre[t];
				while (~i)
					e[i].w -= minn, e[i ^ 1].w += minn, i = pre[e[i ^ 1].to];
				ans += (ll)minn * dis[t];
			}
			return ans;
		}
	}
	int work()
	{
		read(n);
		p1 = (n << 1) + 1, p2 = p1 + 1, p3 = p2 + 1, p4 = p3 + 1, s = p4 + 1, t = s + 1;
		memset(head, -1, sizeof(int[t + 1]));
		for (int i = 1; i <= n; i++)
		{
			int x, y, c;
			read(x), read(y), read(c);
			addtw(i, p1, c, x + y);
			addtw(i, p2, c, x - y);
			addtw(i, p3, c, -x + y);
			addtw(i, p4, c, -x - y);
			addtw(s, i, c, 0);
		}
		for (int i = 1; i <= n; i++)
		{
			int x, y, c;
			read(x), read(y), read(c);
			addtw(p1, i + n, c, -x - y);
			addtw(p2, i + n, c, -x + y);
			addtw(p3, i + n, c, x - y);
			addtw(p4, i + n, c, x + y);
			addtw(i + n, t, c, 0);
		}
		write(EK::EK());
		return 0;
	}
}
int main()
{
	return zyt::work();
}
```