#include<bits/stdc++.h>
using namespace std;
template<unsigned N,unsigned M> struct Maxcost_Maxflow
{
    #define int long long
    int const inf=1e15;
    int target[M],pre[M],last[N],tot=1,flow[M],maxflow,
    cost,deep[N],w[M],ef[M],upd[M],dis[N],pr[N],s,t;
    void add(int x,int y,int z,int co)
    {
        tot++;
        target[tot]=y;
        pre[tot]=last[x];
        last[x]=tot;
        flow[tot]=z;
        w[tot]=co;
        target[++tot]=x;
        pre[tot]=last[y];
        last[y]=tot;
        w[tot]=-co;
    }
    queue<int>q;
    bool inq[N];
    bool spfa()
    {
        q.push(s);
        for(register int i=s;i<=t;i++)
            dis[i]=-inf,ef[i]=inf,pr[i]=0,upd[i]=0;
        dis[s]=0;
        inq[s]=1;
        while(!q.empty())
        {
            int now=q.front();inq[now]=0;q.pop();
            for(register int i=last[now];i;i=pre[i])
            {
                int tar=target[i];
                if(flow[i]&&(dis[now]+w[i]>dis[tar]))
                {
                    dis[tar]=dis[now]+w[i];
                    pr[tar]=now;
                    upd[tar]=i;
                    ef[tar]=min(ef[now],flow[i]);
                    if(!inq[tar])q.push(tar),inq[tar]=1;
                }
            }
        }
        return pr[t];
    }
    void ek()
    {
        while(spfa())
        {
            maxflow+=ef[t];
            cost+=dis[t]*ef[t];
            for(register int i=t;i!=s;i=pr[i])
            {
                flow[upd[i]]-=ef[t];
                flow[upd[i]^1]+=ef[t];
            }
        }
    }
    #undef int
};
Maxcost_Maxflow<4005,400005>g;
int main()
{
    int n,x,y,z;
    scanf("%d",&n);
    g.t=2*n+5;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        g.add(i,2*n+1,1e9,x+y);
        g.add(i,2*n+2,1e9,x-y);
        g.add(i,2*n+3,1e9,-x+y);
        g.add(i,2*n+4,1e9,-x-y);
        g.add(0,i,z,0);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        g.add(2*n+1,i+n,1e9,-x-y);
        g.add(2*n+2,i+n,1e9,-x+y);
        g.add(2*n+3,i+n,1e9,x-y);
        g.add(2*n+4,i+n,1e9,x+y);
        g.add(i+n,g.t,z,0);
    }
    g.ek();
    printf("%lld\n",g.cost);
    return 0;
}
### 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<bits/stdc++.h>
using namespace std;
template<unsigned N,unsigned M> struct Maxcost_Maxflow
{
    #define int long long
    int const inf=1e15;
    int target[M],pre[M],last[N],tot=1,flow[M],maxflow,
    cost,deep[N],w[M],ef[M],upd[M],dis[N],pr[N],s,t;
    void add(int x,int y,int z,int co)
    {
        tot++;
        target[tot]=y;
        pre[tot]=last[x];
        last[x]=tot;
        flow[tot]=z;
        w[tot]=co;
        target[++tot]=x;
        pre[tot]=last[y];
        last[y]=tot;
        w[tot]=-co;
    }
    queue<int>q;
    bool inq[N];
    bool spfa()
    {
        q.push(s);
        for(register int i=s;i<=t;i++)
            dis[i]=-inf,ef[i]=inf,pr[i]=0,upd[i]=0;
        dis[s]=0;
        inq[s]=1;
        while(!q.empty())
        {
            int now=q.front();inq[now]=0;q.pop();
            for(register int i=last[now];i;i=pre[i])
            {
                int tar=target[i];
                if(flow[i]&&(dis[now]+w[i]>dis[tar]))
                {
                    dis[tar]=dis[now]+w[i];
                    pr[tar]=now;
                    upd[tar]=i;
                    ef[tar]=min(ef[now],flow[i]);
                    if(!inq[tar])q.push(tar),inq[tar]=1;
                }
            }
        }
        return pr[t];
    }
    void ek()
    {
        while(spfa())
        {
            maxflow+=ef[t];
            cost+=dis[t]*ef[t];
            for(register int i=t;i!=s;i=pr[i])
            {
                flow[upd[i]]-=ef[t];
                flow[upd[i]^1]+=ef[t];
            }
        }
    }
    #undef int
};
Maxcost_Maxflow<4005,400005>g;
int main()
{
    int n,x,y,z;
    scanf("%d",&n);
    g.t=2*n+5;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        g.add(i,2*n+1,1e9,x+y);
        g.add(i,2*n+2,1e9,x-y);
        g.add(i,2*n+3,1e9,-x+y);
        g.add(i,2*n+4,1e9,-x-y);
        g.add(0,i,z,0);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        g.add(2*n+1,i+n,1e9,-x-y);
        g.add(2*n+2,i+n,1e9,-x+y);
        g.add(2*n+3,i+n,1e9,x-y);
        g.add(2*n+4,i+n,1e9,x+y);
        g.add(i+n,g.t,z,0);
    }
    g.ek();
    printf("%lld\n",g.cost);
    return 0;
}
```