#include <cstdio>
#include <cstring>

#define N 1001
#define V 2020
#define E 20386
#define F 0x7fffffff

#define MIN(A, B) ((A) < (B) ? (A) : (B))

struct edge {
    int u, v;
    long long w;
    int c, x;
} e[E];

const long long y[2][4] = {{-1, 1, -1, 1}, {-1, -1, 1, 1}};

long long p[2][2][N], d[V];
int h[V], m[2][N], f[V], q[V], l, t, z, n, g;
bool v[V];

inline void adde(int u, int v, long long w, int c) {
    e[z] = edge{u, v, -w, c, h[u]}; h[u] = z++;
    e[z] = edge{v, u, w, 0, h[v]}; h[v] = z++;
}

inline void push(int x) {
    q[t++] = x;
    if (t == V) t = 0;
}

inline int pop() {
    int x = q[l++];
    if (l == V) l = 0;
    return x;
}

bool spfa() {
    memset(d, 0x3f, sizeof d);
    d[0] = 0; push(0); v[0] = true;

    while (l != t) {
        int x = pop();
        v[x] = false;

        for (int i = h[x]; ~i; i = e[i].x) {
            if (e[i].c && d[e[i].v] > d[x] + e[i].w) {
                d[e[i].v] = d[x] + e[i].w; f[e[i].v] = i;
                if (!v[e[i].v]) { push(e[i].v); v[e[i].v] = true; }
            }
        }
    }

    return d[g] != 0x3f3f3f3f3f3f3f3fLL;
}

long long solve() {
    long long c = 0;

    while (spfa()) {
        int w = F;
        for (int u = g; u; u = e[f[u]].u) w = MIN(w, e[f[u]].c);

        for (int u = g; u; u = e[f[u]].u) {
            c += e[f[u]].w * w; e[f[u]].c -= w; e[f[u] ^ 1].c += w;
        }
    }

    return -c;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n); g = (n << 1) + 9;
    for (int i = 1; i <= 4; i++) adde((n << 1) + i, (n << 1) + i + 4, 0, F);

    for (int s = 0; s <= 1; s++)
        for (int i = 1; i <= n; i++)
            scanf("%lld%lld%d", &p[s][0][i], &p[s][1][i], &m[s][i]);

    for (int i = 1; i <= n; i++) {
        adde(0, i, 0, m[0][i]); adde(n + i, g, 0, m[1][i]);

        for (int j = 0; j < 4; j++) {
            adde(i, (n << 1) + j + 1, p[0][0][i] * y[0][j] + p[0][1][i] * y[1][j], F);
            adde((n << 1) + 8 - j, n + i, p[1][0][i] * y[0][j] + p[1][1][i] * y[1][j], F);
        }
    }

    printf("%lld\n", solve()); 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 <cstdio>
#include <cstring>

#define N 1001
#define V 2020
#define E 20386
#define F 0x7fffffff

#define MIN(A, B) ((A) < (B) ? (A) : (B))

struct edge {
    int u, v;
    long long w;
    int c, x;
} e[E];

const long long y[2][4] = {{-1, 1, -1, 1}, {-1, -1, 1, 1}};

long long p[2][2][N], d[V];
int h[V], m[2][N], f[V], q[V], l, t, z, n, g;
bool v[V];

inline void adde(int u, int v, long long w, int c) {
    e[z] = edge{u, v, -w, c, h[u]}; h[u] = z++;
    e[z] = edge{v, u, w, 0, h[v]}; h[v] = z++;
}

inline void push(int x) {
    q[t++] = x;
    if (t == V) t = 0;
}

inline int pop() {
    int x = q[l++];
    if (l == V) l = 0;
    return x;
}

bool spfa() {
    memset(d, 0x3f, sizeof d);
    d[0] = 0; push(0); v[0] = true;

    while (l != t) {
        int x = pop();
        v[x] = false;

        for (int i = h[x]; ~i; i = e[i].x) {
            if (e[i].c && d[e[i].v] > d[x] + e[i].w) {
                d[e[i].v] = d[x] + e[i].w; f[e[i].v] = i;
                if (!v[e[i].v]) { push(e[i].v); v[e[i].v] = true; }
            }
        }
    }

    return d[g] != 0x3f3f3f3f3f3f3f3fLL;
}

long long solve() {
    long long c = 0;

    while (spfa()) {
        int w = F;
        for (int u = g; u; u = e[f[u]].u) w = MIN(w, e[f[u]].c);

        for (int u = g; u; u = e[f[u]].u) {
            c += e[f[u]].w * w; e[f[u]].c -= w; e[f[u] ^ 1].c += w;
        }
    }

    return -c;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n); g = (n << 1) + 9;
    for (int i = 1; i <= 4; i++) adde((n << 1) + i, (n << 1) + i + 4, 0, F);

    for (int s = 0; s <= 1; s++)
        for (int i = 1; i <= n; i++)
            scanf("%lld%lld%d", &p[s][0][i], &p[s][1][i], &m[s][i]);

    for (int i = 1; i <= n; i++) {
        adde(0, i, 0, m[0][i]); adde(n + i, g, 0, m[1][i]);

        for (int j = 0; j < 4; j++) {
            adde(i, (n << 1) + j + 1, p[0][0][i] * y[0][j] + p[0][1][i] * y[1][j], F);
            adde((n << 1) + 8 - j, n + i, p[1][0][i] * y[0][j] + p[1][1][i] * y[1][j], F);
        }
    }

    printf("%lld\n", solve()); return 0;
}

```