/*
	  Author : @evenbao
	  Created : 2020 / 07 / 18
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define pii pair<int , int>
#define mp make_pair
#define fi first
#define se second

const int N = 2e5 + 10;
const LL INF = 1e18;

int n , tot , S , T , m , n1 , n2 , n3 , n4;
LL dist[N] , incf[N];
int head[N] , pre[N] , inq[N];
LL ans;

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void read(T &x) {
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

struct Edge {
		int to;
		LL w , cst;
		int nxt;
} E[N << 2];

inline void AddEdge(int u , int v , LL w , LL cost) {
		E[++tot] = (Edge) {v , w , cost , head[u]};  head[u] = tot;
		E[++tot] = (Edge) {u , 0 , -cost , head[v]}; head[v] = tot;
}
inline bool argument() {
		queue < int > Q;
		for (int i = 1; i <= m; ++i) {
				dist[i] = incf[i] = -INF;
				inq[i] = false;
		}
		Q.push(S); incf[S] = INF; dist[S] = 0; pre[S] = 0;
		while (!Q.empty()) {
				int u = Q.front(); Q.pop(); inq[u] = false;
				for (int i = head[u]; i; i = E[i].nxt) {
						int v = E[i].to;
						LL w = E[i].w , cst = E[i].cst;
						if (dist[u] + (LL) cst > dist[v] && w > 0) {
								dist[v] = dist[u] + (LL) cst;
								incf[v] = min(incf[u] , (LL) w);
								pre[v] = i;
								if (!inq[v]) {
										inq[v] = true;
										Q.push(v);
								}
						}
				}
		}
		if (dist[T] > -INF) return true;
		else return false;
}
inline void update() {
		int now = T;
		while (now > 0) {
				E[pre[now]].w -= incf[T];
				E[pre[now] ^ 1].w += incf[T];
				now = E[pre[now] ^ 1].to;
		}
		ans += (LL) dist[T] * incf[T];
		return;
}
int main() {
		
		read(n); tot = 1;
		m = 2 * n + 6; S = 2 * n + 1 , T = 2 * n + 2;
		n1 = 2 * n + 3 , n2 = 2 * n + 4 , n3 = 2 * n + 5 , n4 = 2 * n + 6;
		for (int i = 1; i <= n; ++i) {
				int rx , ry , rc;
				read(rx) , read(ry) , read(rc);
				AddEdge(S , i , rc , 0);
				AddEdge(i , n1 , INF , rx + ry);
				AddEdge(i , n2 , INF , -rx + ry);
				AddEdge(i , n3 , INF , rx - ry);
				AddEdge(i , n4 , INF , -rx - ry);
		}
		for (int i = 1; i <= n; ++i) {
				int rx , ry , rc;
				read(rx) , read(ry) , read(rc);
				AddEdge(i + n , T , rc , 0);
				AddEdge(n1 , i + n , INF , -rx - ry);
				AddEdge(n2 , i + n , INF , rx - ry);
				AddEdge(n3 , i + n , INF , -rx + ry);
				AddEdge(n4 , i + n , INF , rx + ry);
		}
		while (argument()) update();
		printf("%lld\n" , ans);		
	  return 0;
}


### Prompt

In Cpp, your task is to solve 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
/*
	  Author : @evenbao
	  Created : 2020 / 07 / 18
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define pii pair<int , int>
#define mp make_pair
#define fi first
#define se second

const int N = 2e5 + 10;
const LL INF = 1e18;

int n , tot , S , T , m , n1 , n2 , n3 , n4;
LL dist[N] , incf[N];
int head[N] , pre[N] , inq[N];
LL ans;

template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void read(T &x) {
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

struct Edge {
		int to;
		LL w , cst;
		int nxt;
} E[N << 2];

inline void AddEdge(int u , int v , LL w , LL cost) {
		E[++tot] = (Edge) {v , w , cost , head[u]};  head[u] = tot;
		E[++tot] = (Edge) {u , 0 , -cost , head[v]}; head[v] = tot;
}
inline bool argument() {
		queue < int > Q;
		for (int i = 1; i <= m; ++i) {
				dist[i] = incf[i] = -INF;
				inq[i] = false;
		}
		Q.push(S); incf[S] = INF; dist[S] = 0; pre[S] = 0;
		while (!Q.empty()) {
				int u = Q.front(); Q.pop(); inq[u] = false;
				for (int i = head[u]; i; i = E[i].nxt) {
						int v = E[i].to;
						LL w = E[i].w , cst = E[i].cst;
						if (dist[u] + (LL) cst > dist[v] && w > 0) {
								dist[v] = dist[u] + (LL) cst;
								incf[v] = min(incf[u] , (LL) w);
								pre[v] = i;
								if (!inq[v]) {
										inq[v] = true;
										Q.push(v);
								}
						}
				}
		}
		if (dist[T] > -INF) return true;
		else return false;
}
inline void update() {
		int now = T;
		while (now > 0) {
				E[pre[now]].w -= incf[T];
				E[pre[now] ^ 1].w += incf[T];
				now = E[pre[now] ^ 1].to;
		}
		ans += (LL) dist[T] * incf[T];
		return;
}
int main() {
		
		read(n); tot = 1;
		m = 2 * n + 6; S = 2 * n + 1 , T = 2 * n + 2;
		n1 = 2 * n + 3 , n2 = 2 * n + 4 , n3 = 2 * n + 5 , n4 = 2 * n + 6;
		for (int i = 1; i <= n; ++i) {
				int rx , ry , rc;
				read(rx) , read(ry) , read(rc);
				AddEdge(S , i , rc , 0);
				AddEdge(i , n1 , INF , rx + ry);
				AddEdge(i , n2 , INF , -rx + ry);
				AddEdge(i , n3 , INF , rx - ry);
				AddEdge(i , n4 , INF , -rx - ry);
		}
		for (int i = 1; i <= n; ++i) {
				int rx , ry , rc;
				read(rx) , read(ry) , read(rc);
				AddEdge(i + n , T , rc , 0);
				AddEdge(n1 , i + n , INF , -rx - ry);
				AddEdge(n2 , i + n , INF , rx - ry);
				AddEdge(n3 , i + n , INF , -rx + ry);
				AddEdge(n4 , i + n , INF , rx + ry);
		}
		while (argument()) update();
		printf("%lld\n" , ans);		
	  return 0;
}


```