#include<bits/stdc++.h>
#define Fail puts("NO"),exit(0);
#define eps 1e-10
#define maxn 1010
#define maxm 100010
#define inf 1000000007
#define mod 998244353
#define pi acos(-1)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef bitset<maxn> bit;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,p1,p2,p3,p4,s,t;
int head[maxn*2],nxt[maxn*20],to[maxn*20],c[maxn*20],v[maxn*20],tot=1;
void add(int x,int y,int z,int u)
{
    ++tot;
    nxt[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    c[tot]=z;
    v[tot]=u;
}
void addx(int x,int y,int z,int u)
{
    add(x,y,z,u);
    add(y,x,0,-u);
}
ll ans;
ll dis[maxn*2];
int pre[maxn*2],pre_num[maxn*2],vis[maxn*2];
queue<int>q;
int spfa()
{
    for(int i=1;i<=t;i++)  dis[i]=-1e16;
    q.push(s);dis[s]=0;vis[s]=1;
    while(q.size())
    {
        int now=q.front();q.pop();vis[now]=0;
        for(int i=head[now];i;i=nxt[i])
        {
            if(dis[to[i]]<dis[now]+v[i]&&c[i])
            {
                dis[to[i]]=dis[now]+v[i];
                pre[to[i]]=now;
                pre_num[to[i]]=i;
                if(!vis[to[i]])  q.push(to[i]),vis[to[i]]=1;
            }
        }
    }
    if(dis[t]==-1e16)  return 0;
    int di=inf;
    for(int i=t;i!=s;i=pre[i])  di=min(di,c[pre_num[i]]);
    for(int i=t;i!=s;i=pre[i])  c[pre_num[i]]-=di,c[pre_num[i]^1]+=di;
    ans+=dis[t]*di;
    return di;
}
int main()
{
    n=read();p1=2*n+1;p2=p1+1;p3=p2+1;p4=p3+1;s=p4+1;t=s+1;
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(s,i,z,0);
        addx(i,p1,inf,x+y);
        addx(i,p2,inf,x-y);
        addx(i,p3,inf,-x+y);
        addx(i,p4,inf,-x-y);
    }
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(i+n,t,z,0);
        addx(p1,i+n,inf,-x-y);
        addx(p2,i+n,inf,-x+y);
        addx(p3,i+n,inf,x-y);
        addx(p4,i+n,inf,x+y);
    }
    while(spfa()){};
    printf("%lld\n",ans);
    return 0;
}
### Prompt

Please provide a Cpp coded solution 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<bits/stdc++.h>
#define Fail puts("NO"),exit(0);
#define eps 1e-10
#define maxn 1010
#define maxm 100010
#define inf 1000000007
#define mod 998244353
#define pi acos(-1)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef bitset<maxn> bit;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,p1,p2,p3,p4,s,t;
int head[maxn*2],nxt[maxn*20],to[maxn*20],c[maxn*20],v[maxn*20],tot=1;
void add(int x,int y,int z,int u)
{
    ++tot;
    nxt[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    c[tot]=z;
    v[tot]=u;
}
void addx(int x,int y,int z,int u)
{
    add(x,y,z,u);
    add(y,x,0,-u);
}
ll ans;
ll dis[maxn*2];
int pre[maxn*2],pre_num[maxn*2],vis[maxn*2];
queue<int>q;
int spfa()
{
    for(int i=1;i<=t;i++)  dis[i]=-1e16;
    q.push(s);dis[s]=0;vis[s]=1;
    while(q.size())
    {
        int now=q.front();q.pop();vis[now]=0;
        for(int i=head[now];i;i=nxt[i])
        {
            if(dis[to[i]]<dis[now]+v[i]&&c[i])
            {
                dis[to[i]]=dis[now]+v[i];
                pre[to[i]]=now;
                pre_num[to[i]]=i;
                if(!vis[to[i]])  q.push(to[i]),vis[to[i]]=1;
            }
        }
    }
    if(dis[t]==-1e16)  return 0;
    int di=inf;
    for(int i=t;i!=s;i=pre[i])  di=min(di,c[pre_num[i]]);
    for(int i=t;i!=s;i=pre[i])  c[pre_num[i]]-=di,c[pre_num[i]^1]+=di;
    ans+=dis[t]*di;
    return di;
}
int main()
{
    n=read();p1=2*n+1;p2=p1+1;p3=p2+1;p4=p3+1;s=p4+1;t=s+1;
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(s,i,z,0);
        addx(i,p1,inf,x+y);
        addx(i,p2,inf,x-y);
        addx(i,p3,inf,-x+y);
        addx(i,p4,inf,-x-y);
    }
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(i+n,t,z,0);
        addx(p1,i+n,inf,-x-y);
        addx(p2,i+n,inf,-x+y);
        addx(p3,i+n,inf,x-y);
        addx(p4,i+n,inf,x+y);
    }
    while(spfa()){};
    printf("%lld\n",ans);
    return 0;
}
```