#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, b, a) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

template <typename T>
struct MinCostFlow {
  struct Edge {
    int u, v;
    T c, w, f;
  };
  const T eps = T(1e-9), INF = numeric_limits<T>::max();
  vector<Edge> E;
  int n, src, sink;
  vector<vector<int>> G;
  T flow = T(), cost = T();
  MinCostFlow(int n, int src, int sink) : n(n), src(src), sink(sink), G(n) {}

  void clear_flow() {
    for (auto& e : E) e.f = T();
    flow = cost = T();
  }
  void reduce() {
    for (auto& e : E) e.c -= e.f;
  }
  void add_edge(int u, int v, T cap, T cost) {
    assert(0 <= u && u < n && 0 <= v && v < n);
    G[u].push_back(E.size()), E.push_back({u, v, cap, cost, T()});
    G[v].push_back(E.size()), E.push_back({v, u, 0, -cost, T()});
  }
  T min_cost_flow(T f = -1) {
    if (f < 0) f = INF;
    if (flow > f) clear_flow();
    f -= flow;
    while (f > eps) {
      vector<T> D(n, INF);
      vector<int> Inq(n), P(n);
      queue<int> Q;
      Q.push(src), D[src] = T(), Inq[src] = 1;
      while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), Inq[u] = 0;
        for (auto i : G[u]) {
          const auto& e = E[i];
          if (e.c - e.f > eps && D[e.v] > D[u] + e.w) {
            D[e.v] = D[u] + e.w, P[e.v] = i;
            if (!Inq[e.v]) Q.push(e.v), Inq[e.v] = 1;
          }
        }
      }
      if (D[sink] == INF) break;
      T can = f;
      for (int u = sink; u != src; u = E[P[u]].u) can = min(can, E[P[u]].c - E[P[u]].f);
      f -= can, flow += can, cost += D[sink] * can;
      for (int u = sink; u != src; u = E[P[u]].u) E[P[u]].f += can, E[P[u] ^ 1].f -= can;
    }
    return cost;
  }
};

const int N = 1005;
int n, RX[N], RY[N], BX[N], BY[N], RC[N], BC[N];

int main() {
  scanf("%d", &n);
  int src = 0, sink = n + n + 5;
  MinCostFlow<LL> mc(n + n + 6, src, sink);
  FI(i, 1, n) scanf("%d%d%d", &RX[i], &RY[i], &RC[i]);
  FI(i, 1, n) scanf("%d%d%d", &BX[i], &BY[i], &BC[i]);
  FI(i, 1, n) {
    mc.add_edge(src, i, RC[i], 0LL);
    mc.add_edge(i + n, sink, BC[i], 0LL);
  }
  FI(i, 1, n) {
    mc.add_edge(i, n + n + 1, RC[i], -(RX[i] + RY[i]));
    mc.add_edge(i, n + n + 2, RC[i], -(RX[i] - RY[i]));
    mc.add_edge(i, n + n + 3, RC[i], -(-RX[i] + RY[i]));
    mc.add_edge(i, n + n + 4, RC[i], -(-RX[i] - RY[i]));
  }
  FI(i, 1, n) {
    mc.add_edge(n + n + 1, i + n, BC[i], (BX[i] + BY[i]));
    mc.add_edge(n + n + 2, i + n, BC[i], (BX[i] - BY[i]));
    mc.add_edge(n + n + 3, i + n, BC[i], (-BX[i] + BY[i]));
    mc.add_edge(n + n + 4, i + n, BC[i], (-BX[i] - BY[i]));
  }
  cout << -mc.min_cost_flow() << endl;
}

### Prompt

Your challenge is to write 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;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, b, a) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

template <typename T>
struct MinCostFlow {
  struct Edge {
    int u, v;
    T c, w, f;
  };
  const T eps = T(1e-9), INF = numeric_limits<T>::max();
  vector<Edge> E;
  int n, src, sink;
  vector<vector<int>> G;
  T flow = T(), cost = T();
  MinCostFlow(int n, int src, int sink) : n(n), src(src), sink(sink), G(n) {}

  void clear_flow() {
    for (auto& e : E) e.f = T();
    flow = cost = T();
  }
  void reduce() {
    for (auto& e : E) e.c -= e.f;
  }
  void add_edge(int u, int v, T cap, T cost) {
    assert(0 <= u && u < n && 0 <= v && v < n);
    G[u].push_back(E.size()), E.push_back({u, v, cap, cost, T()});
    G[v].push_back(E.size()), E.push_back({v, u, 0, -cost, T()});
  }
  T min_cost_flow(T f = -1) {
    if (f < 0) f = INF;
    if (flow > f) clear_flow();
    f -= flow;
    while (f > eps) {
      vector<T> D(n, INF);
      vector<int> Inq(n), P(n);
      queue<int> Q;
      Q.push(src), D[src] = T(), Inq[src] = 1;
      while (!Q.empty()) {
        int u = Q.front();
        Q.pop(), Inq[u] = 0;
        for (auto i : G[u]) {
          const auto& e = E[i];
          if (e.c - e.f > eps && D[e.v] > D[u] + e.w) {
            D[e.v] = D[u] + e.w, P[e.v] = i;
            if (!Inq[e.v]) Q.push(e.v), Inq[e.v] = 1;
          }
        }
      }
      if (D[sink] == INF) break;
      T can = f;
      for (int u = sink; u != src; u = E[P[u]].u) can = min(can, E[P[u]].c - E[P[u]].f);
      f -= can, flow += can, cost += D[sink] * can;
      for (int u = sink; u != src; u = E[P[u]].u) E[P[u]].f += can, E[P[u] ^ 1].f -= can;
    }
    return cost;
  }
};

const int N = 1005;
int n, RX[N], RY[N], BX[N], BY[N], RC[N], BC[N];

int main() {
  scanf("%d", &n);
  int src = 0, sink = n + n + 5;
  MinCostFlow<LL> mc(n + n + 6, src, sink);
  FI(i, 1, n) scanf("%d%d%d", &RX[i], &RY[i], &RC[i]);
  FI(i, 1, n) scanf("%d%d%d", &BX[i], &BY[i], &BC[i]);
  FI(i, 1, n) {
    mc.add_edge(src, i, RC[i], 0LL);
    mc.add_edge(i + n, sink, BC[i], 0LL);
  }
  FI(i, 1, n) {
    mc.add_edge(i, n + n + 1, RC[i], -(RX[i] + RY[i]));
    mc.add_edge(i, n + n + 2, RC[i], -(RX[i] - RY[i]));
    mc.add_edge(i, n + n + 3, RC[i], -(-RX[i] + RY[i]));
    mc.add_edge(i, n + n + 4, RC[i], -(-RX[i] - RY[i]));
  }
  FI(i, 1, n) {
    mc.add_edge(n + n + 1, i + n, BC[i], (BX[i] + BY[i]));
    mc.add_edge(n + n + 2, i + n, BC[i], (BX[i] - BY[i]));
    mc.add_edge(n + n + 3, i + n, BC[i], (-BX[i] + BY[i]));
    mc.add_edge(n + n + 4, i + n, BC[i], (-BX[i] - BY[i]));
  }
  cout << -mc.min_cost_flow() << endl;
}

```