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

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

#define MAXN 50000
#define MAXM 1000000
#define INF 1ll<<60
#define LL long long
struct Edge{
    LL w,c;
    int v,Next;
}E[MAXM+5];
int Adj[MAXN+5],ecnt;
void AddEdge(int u,int v,LL Cap,LL Cost){
    E[ecnt].v=v,E[ecnt].w=Cap,E[ecnt].c= Cost,E[ecnt].Next=Adj[u],Adj[u]=ecnt++;
    E[ecnt].v=u,E[ecnt].w=0,  E[ecnt].c=-Cost,E[ecnt].Next=Adj[v],Adj[v]=ecnt++;
}

int pre[MAXN+5];
LL Dist[MAXN+5];
bool vis[MAXN+5];
int cnt[MAXN+5];
bool SPFA(int S,int T,int N,LL &Flow,LL &Cost){
    for(int i=0;i<=N;i++)
        Dist[i]=INF,pre[i]=-1,vis[i]=0,cnt[i]=0;
    queue<int> Q;
    Q.push(S);
    Dist[S]=0,vis[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop();vis[u]=0;
        for(int i=Adj[u];i!=-1;i=E[i].Next){
            int v=E[i].v,c=E[i].c;
            if(E[i].w&&Dist[v]>Dist[u]+c){
                Dist[v]=Dist[u]+c;
                pre[v]=i;
                if(!vis[v]){
                    ++cnt[v];
                    vis[v]=1,Q.push(v);
                }
            }
        }
    }
    if(Dist[T]==INF)
        return 0;
    LL Min=INF;
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        Min=min(Min,(LL)E[i].w);
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        E[i].w-=Min,E[i^1].w+=Min,Cost+=Min*E[i].c;
    Flow+=Min;
    return 1;
}
pair<LL,LL> Dinic(int S,int T,int N){
    LL Flow=0,Cost=0;
    while(1)
        if(!SPFA(S,T,N,Flow,Cost))
            break;
    return make_pair(Flow,Cost);
}

#undef MAXN
#undef MAXM

#define MAXM 1000
int N,M,K;
int A[MAXM+5];

int main(){
    N=read();
    ecnt=0;
    memset(Adj,-1,sizeof Adj);
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(1,i+1,c,0);
        AddEdge(i+1,N+2,INF,x+y);
        AddEdge(i+1,N+3,INF,-x+y);
        AddEdge(i+1,N+4,INF,x-y);
        AddEdge(i+1,N+5,INF,-x-y);
    }
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(i+5+N,2*N+6,c,0);
        AddEdge(N+2,i+5+N,INF,-x-y);
        AddEdge(N+3,i+5+N,INF,x-y);
        AddEdge(N+4,i+5+N,INF,-x+y);
        AddEdge(N+5,i+5+N,INF,x+y);
    }
    printf("%lld",-Dinic(1,2*N+6,2*N+6).second);
    return 0;
}

### Prompt

Please create a solution in Cpp 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
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

#define MAXN 50000
#define MAXM 1000000
#define INF 1ll<<60
#define LL long long
struct Edge{
    LL w,c;
    int v,Next;
}E[MAXM+5];
int Adj[MAXN+5],ecnt;
void AddEdge(int u,int v,LL Cap,LL Cost){
    E[ecnt].v=v,E[ecnt].w=Cap,E[ecnt].c= Cost,E[ecnt].Next=Adj[u],Adj[u]=ecnt++;
    E[ecnt].v=u,E[ecnt].w=0,  E[ecnt].c=-Cost,E[ecnt].Next=Adj[v],Adj[v]=ecnt++;
}

int pre[MAXN+5];
LL Dist[MAXN+5];
bool vis[MAXN+5];
int cnt[MAXN+5];
bool SPFA(int S,int T,int N,LL &Flow,LL &Cost){
    for(int i=0;i<=N;i++)
        Dist[i]=INF,pre[i]=-1,vis[i]=0,cnt[i]=0;
    queue<int> Q;
    Q.push(S);
    Dist[S]=0,vis[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop();vis[u]=0;
        for(int i=Adj[u];i!=-1;i=E[i].Next){
            int v=E[i].v,c=E[i].c;
            if(E[i].w&&Dist[v]>Dist[u]+c){
                Dist[v]=Dist[u]+c;
                pre[v]=i;
                if(!vis[v]){
                    ++cnt[v];
                    vis[v]=1,Q.push(v);
                }
            }
        }
    }
    if(Dist[T]==INF)
        return 0;
    LL Min=INF;
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        Min=min(Min,(LL)E[i].w);
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        E[i].w-=Min,E[i^1].w+=Min,Cost+=Min*E[i].c;
    Flow+=Min;
    return 1;
}
pair<LL,LL> Dinic(int S,int T,int N){
    LL Flow=0,Cost=0;
    while(1)
        if(!SPFA(S,T,N,Flow,Cost))
            break;
    return make_pair(Flow,Cost);
}

#undef MAXN
#undef MAXM

#define MAXM 1000
int N,M,K;
int A[MAXM+5];

int main(){
    N=read();
    ecnt=0;
    memset(Adj,-1,sizeof Adj);
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(1,i+1,c,0);
        AddEdge(i+1,N+2,INF,x+y);
        AddEdge(i+1,N+3,INF,-x+y);
        AddEdge(i+1,N+4,INF,x-y);
        AddEdge(i+1,N+5,INF,-x-y);
    }
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(i+5+N,2*N+6,c,0);
        AddEdge(N+2,i+5+N,INF,-x-y);
        AddEdge(N+3,i+5+N,INF,x-y);
        AddEdge(N+4,i+5+N,INF,-x+y);
        AddEdge(N+5,i+5+N,INF,x+y);
    }
    printf("%lld",-Dinic(1,2*N+6,2*N+6).second);
    return 0;
}

```