#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,s,t) for(int i=s;i<t;i++)
typedef pair<long long, int> pli;
typedef long long ll;
const int maxn = 2222;
const ll inf = 1e18;
struct edge {
    int v, f, c, rev;
};
int nodenum,stnode,ednode, prep[maxn + 5], pree[maxn + 5];ll dis[maxn+5],h[maxn+5];
vector<edge> e[maxn + 5];
void addedge(int from, int to, int cap, int cost) {
    e[from].push_back({to, cap, cost, (int)e[to].size()});
    e[to].push_back({from, 0, -cost, (int)e[from].size() - 1});
}

ll flow,cost;
void mincostflow() {
    fill(h, h + 1 + nodenum, 0);
    flow=cost=0;
    while (1) {
        priority_queue <pli, vector<pli>, greater<pli> > q;
        fill(dis, dis + 1 + nodenum, inf);
        dis[stnode] = 0; q.push({0,stnode});
        while (!q.empty()) {
            pli now = q.top(); q.pop();
            int v = now.se;
            if (dis[v] < now.fi)continue;
            for (int i = 0; i < e[v].size(); ++i) {
                edge& ee = e[v][i];
                if (ee.f > 0 && dis[ee.v] > dis[v] + ee.c + h[v] - h[ee.v]) {
                    dis[ee.v] = dis[v] + ee.c + h[v] - h[ee.v];
                    prep[ee.v] = v;pree[ee.v] = i;
                    q.push({dis[ee.v], ee.v});
                }
            }
        }
        if (dis[ednode] == inf)break;
        for (int i = 1; i <= nodenum; ++i)h[i] += dis[i];
        ll d = inf;
        for (int v = ednode; v != stnode; v = prep[v])
            d = min(d, (ll)e[prep[v]][pree[v]].f);
        flow += d; cost += d*h[ednode];
        for (int v = ednode; v != stnode; v = prep[v]) {
            edge& ee = e[prep[v]][pree[v]];
            ee.f -= d;
            e[v][ee.rev].f += d;
        }
    }
}
int dir[4][2]={1,1,-1,-1,1,-1,-1,1};
int main()
{
    int n,a,b,c;scanf("%d",&n);
    int tmp=n*2;
    nodenum=n*2+2+4,stnode=nodenum,ednode=nodenum-1;
    rep(i,1,n+1)
    {
        scanf("%d%d%d",&b,&c,&a),addedge(stnode,i,a,0);
        rep(j,0,4)addedge(i,tmp+j+1,a,b*dir[j][0]+c*dir[j][1]);
    }
    rep(i,1,n+1)
    {
        scanf("%d%d%d",&b,&c,&a),addedge(i+n,ednode,a,0);
        rep(j,0,4)addedge(tmp+j+1,i+n,a,-b*dir[j][0]-c*dir[j][1]);
    }
    mincostflow();
    printf("%lld\n",-cost);
}
### Prompt

Generate a CPP solution 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<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i,s,t) for(int i=s;i<t;i++)
typedef pair<long long, int> pli;
typedef long long ll;
const int maxn = 2222;
const ll inf = 1e18;
struct edge {
    int v, f, c, rev;
};
int nodenum,stnode,ednode, prep[maxn + 5], pree[maxn + 5];ll dis[maxn+5],h[maxn+5];
vector<edge> e[maxn + 5];
void addedge(int from, int to, int cap, int cost) {
    e[from].push_back({to, cap, cost, (int)e[to].size()});
    e[to].push_back({from, 0, -cost, (int)e[from].size() - 1});
}

ll flow,cost;
void mincostflow() {
    fill(h, h + 1 + nodenum, 0);
    flow=cost=0;
    while (1) {
        priority_queue <pli, vector<pli>, greater<pli> > q;
        fill(dis, dis + 1 + nodenum, inf);
        dis[stnode] = 0; q.push({0,stnode});
        while (!q.empty()) {
            pli now = q.top(); q.pop();
            int v = now.se;
            if (dis[v] < now.fi)continue;
            for (int i = 0; i < e[v].size(); ++i) {
                edge& ee = e[v][i];
                if (ee.f > 0 && dis[ee.v] > dis[v] + ee.c + h[v] - h[ee.v]) {
                    dis[ee.v] = dis[v] + ee.c + h[v] - h[ee.v];
                    prep[ee.v] = v;pree[ee.v] = i;
                    q.push({dis[ee.v], ee.v});
                }
            }
        }
        if (dis[ednode] == inf)break;
        for (int i = 1; i <= nodenum; ++i)h[i] += dis[i];
        ll d = inf;
        for (int v = ednode; v != stnode; v = prep[v])
            d = min(d, (ll)e[prep[v]][pree[v]].f);
        flow += d; cost += d*h[ednode];
        for (int v = ednode; v != stnode; v = prep[v]) {
            edge& ee = e[prep[v]][pree[v]];
            ee.f -= d;
            e[v][ee.rev].f += d;
        }
    }
}
int dir[4][2]={1,1,-1,-1,1,-1,-1,1};
int main()
{
    int n,a,b,c;scanf("%d",&n);
    int tmp=n*2;
    nodenum=n*2+2+4,stnode=nodenum,ednode=nodenum-1;
    rep(i,1,n+1)
    {
        scanf("%d%d%d",&b,&c,&a),addedge(stnode,i,a,0);
        rep(j,0,4)addedge(i,tmp+j+1,a,b*dir[j][0]+c*dir[j][1]);
    }
    rep(i,1,n+1)
    {
        scanf("%d%d%d",&b,&c,&a),addedge(i+n,ednode,a,0);
        rep(j,0,4)addedge(tmp+j+1,i+n,a,-b*dir[j][0]-c*dir[j][1]);
    }
    mincostflow();
    printf("%lld\n",-cost);
}
```