#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
inline int read()
{
	int x = 0 , f = 1; char ch = getchar();
	while(ch < '0' || ch > '9')	{if(ch == '-')	f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 2e5 + 50 , inf = 1e8;
const ll INF = 1e18;
int n , s , t;
namespace Dinic
{
	struct Edge
	{
		int to , cap , dis; Edge *nxt , *pre;
		Edge(int to = 0,int cap = 0,int dis = 0,Edge *nxt = NULL) : to(to) , cap(cap) , dis(dis) , nxt(nxt) { pre = NULL;}
	} *head[N] , pool[N << 2] , *tail = pool , *cur[N];
	inline void add(int u,int v,int w,int f) { head[u] = new (tail ++) Edge(v,w,f,head[u]); head[v] = new (tail ++) Edge(u,0,-f,head[v]); head[u] -> pre = head[v]; head[v] -> pre = head[u];}
	ll dis[N];
	bool vis[N];
	inline bool spfa()
	{
		for(int i = 0;i <= t;i ++) dis[i] = -INF , vis[i] = 0;
		std::queue<int> q; q.push(s); dis[s] = 0;
		while(!q.empty())
		{
			int x = q.front(); q.pop(); vis[x] = 0;
			for(Edge *i = head[x];i;i = i -> nxt)
			{
				int to = i -> to;
				if(i -> cap && dis[to] < dis[x] + i -> dis)
				{
					dis[to] = dis[x] + i -> dis;
					if(!vis[to]) q.push(to) , vis[to] = 1;
				}
			}
		}
		return dis[t] > -inf;
	}
	int dfs(int x,int want)
	{
		if(x == t || !want) return want;
		int get = 0 , flow; vis[x] = 1;
		for(Edge *&i = cur[x];i;i = i -> nxt)
		{
			int to = i -> to;
			if(!vis[to] && dis[to] == dis[x] + i -> dis && (flow = dfs(to,min(i -> cap,want))))
			{
				i -> cap -= flow; i -> pre -> cap += flow;
				get += flow; want -= flow;
				if(!want) break;
			}
		}
		return get;
	}
	inline ll zkw()
	{
		ll ans = 0;
		while(spfa())
		{
			vis[t] = 1;
			while(vis[t])
			{
				for(int i = 0;i <= t;i ++) cur[i] = head[i] , vis[i] = 0;
				ans += dis[t] * dfs(s,inf);
			}
		}
		return ans;
	}
}
using namespace Dinic;
int main()
{
	n = read(); int p1 = 2 * n + 1 , p2 = p1 + 1 , p3 = p2 + 1 , p4 = p3 + 1; t = p4 + 1;
	for(int i = 1;i <= n;i ++)
	{
		int x = read() , y = read() , w = read();
		add(s,i,w,0);
		add(i,p1,inf,x + y);
		add(i,p2,inf,x - y);
		add(i,p3,inf,y - x);
		add(i,p4,inf,-x - y);
	}
	for(int i = 1;i <= n;i ++)
	{
		int x = read() , y = read() , w = read();
		add(n + i,t,w,0);
		add(p1,n + i,inf,-x - y);
		add(p2,n + i,inf,y - x);
		add(p3,n + i,inf,x - y);
		add(p4,n + i,inf,x + y);
	}
	printf("%lld\n",zkw());
}
### 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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
inline int read()
{
	int x = 0 , f = 1; char ch = getchar();
	while(ch < '0' || ch > '9')	{if(ch == '-')	f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 2e5 + 50 , inf = 1e8;
const ll INF = 1e18;
int n , s , t;
namespace Dinic
{
	struct Edge
	{
		int to , cap , dis; Edge *nxt , *pre;
		Edge(int to = 0,int cap = 0,int dis = 0,Edge *nxt = NULL) : to(to) , cap(cap) , dis(dis) , nxt(nxt) { pre = NULL;}
	} *head[N] , pool[N << 2] , *tail = pool , *cur[N];
	inline void add(int u,int v,int w,int f) { head[u] = new (tail ++) Edge(v,w,f,head[u]); head[v] = new (tail ++) Edge(u,0,-f,head[v]); head[u] -> pre = head[v]; head[v] -> pre = head[u];}
	ll dis[N];
	bool vis[N];
	inline bool spfa()
	{
		for(int i = 0;i <= t;i ++) dis[i] = -INF , vis[i] = 0;
		std::queue<int> q; q.push(s); dis[s] = 0;
		while(!q.empty())
		{
			int x = q.front(); q.pop(); vis[x] = 0;
			for(Edge *i = head[x];i;i = i -> nxt)
			{
				int to = i -> to;
				if(i -> cap && dis[to] < dis[x] + i -> dis)
				{
					dis[to] = dis[x] + i -> dis;
					if(!vis[to]) q.push(to) , vis[to] = 1;
				}
			}
		}
		return dis[t] > -inf;
	}
	int dfs(int x,int want)
	{
		if(x == t || !want) return want;
		int get = 0 , flow; vis[x] = 1;
		for(Edge *&i = cur[x];i;i = i -> nxt)
		{
			int to = i -> to;
			if(!vis[to] && dis[to] == dis[x] + i -> dis && (flow = dfs(to,min(i -> cap,want))))
			{
				i -> cap -= flow; i -> pre -> cap += flow;
				get += flow; want -= flow;
				if(!want) break;
			}
		}
		return get;
	}
	inline ll zkw()
	{
		ll ans = 0;
		while(spfa())
		{
			vis[t] = 1;
			while(vis[t])
			{
				for(int i = 0;i <= t;i ++) cur[i] = head[i] , vis[i] = 0;
				ans += dis[t] * dfs(s,inf);
			}
		}
		return ans;
	}
}
using namespace Dinic;
int main()
{
	n = read(); int p1 = 2 * n + 1 , p2 = p1 + 1 , p3 = p2 + 1 , p4 = p3 + 1; t = p4 + 1;
	for(int i = 1;i <= n;i ++)
	{
		int x = read() , y = read() , w = read();
		add(s,i,w,0);
		add(i,p1,inf,x + y);
		add(i,p2,inf,x - y);
		add(i,p3,inf,y - x);
		add(i,p4,inf,-x - y);
	}
	for(int i = 1;i <= n;i ++)
	{
		int x = read() , y = read() , w = read();
		add(n + i,t,w,0);
		add(p1,n + i,inf,-x - y);
		add(p2,n + i,inf,y - x);
		add(p3,n + i,inf,x - y);
		add(p4,n + i,inf,x + y);
	}
	printf("%lld\n",zkw());
}
```