#include <bits/stdc++.h>
using namespace std;
using ll = long long;

namespace {
  ll read() {
    ll x;
    cin >> x;
    return x;
  }

  string reads() {
    string s;
    cin >> s;
    return s;
  }

  template<class T>
  void write(T x) {
    cout << x << ' ';
  }

  void newline() {
    cout << '\n';
  }
}

struct mincostflow {
  struct edge {
    int v;
    long long c;
    long long w;
    int r;
  };

  vector<vector<edge>> G;

  mincostflow(int n) : G(n) {}

  void add(int u, int v, long long c, long long w) {
    int i = G[u].size();
    int j = G[v].size();
    G[u].push_back({v, c, w, j});
    G[v].push_back({u, 0, -w, i});
  }

  long long run(int s, int t, long long f) {
    const int N = G.size();
    long long res = 0;
    vector<long long> H(N);
    vector<long long> D(N);
    const long long INF = 1e18;
    vector<int> PE(N), PV(N);
    while (f > 0) {
      priority_queue<pair<long long, int>> q;
      fill(D.begin(), D.end(), INF);
      D[s] = 0;
      q.emplace(0, s);
      while (!q.empty()) {
        long long d = -q.top().first;
        int u = q.top().second;
        q.pop();
        if (D[u] < d) continue;
        for (int i = 0; i < G[u].size(); i++) {
          edge e = G[u][i];
          if (e.c > 0 && D[e.v] > D[u] + e.w + H[u] - H[e.v]) {
            D[e.v] = D[u] + e.w + H[u] - H[e.v];
            q.emplace(-D[e.v], e.v);
            PV[e.v] = u;
            PE[e.v] = i;
          }
        }
      }
      if (D[t] == INF) return -1;
      for (int i = 0; i < N; i++) H[i] += D[i];
      long long d = f;
      for (int i = t; i != s; i = PV[i]) {
        d = min(d, G[PV[i]][PE[i]].c);
      }
      f -= d;
      res += d * H[t];
      for (int i = t; i != s; i = PV[i]) {
        edge &e = G[PV[i]][PE[i]];
        e.c -= d;
        G[i][e.r].c += d;
      }
    }
    return res;
  }
};

int main() {
  int N = read();
  mincostflow mcf(N * 2 + 6);
  int s = N * 2 + 4;
  int t = N * 2 + 5;
  const ll INF = 1e10;
  int sum = 0;
  for (int i = 0; i < N; i++) {
    ll x = read(), y = read(), c = read();
    sum += c;
    mcf.add(s, i, c, 0);
    mcf.add(i, N * 2 + 0, 1e9, +x + y + INF);
    mcf.add(i, N * 2 + 1, 1e9, +x - y + INF);
    mcf.add(i, N * 2 + 2, 1e9, -x + y + INF);
    mcf.add(i, N * 2 + 3, 1e9, -x - y + INF);
  }
  for (int i = 0; i < N; i++) {
    ll x = read(), y = read(), c = read();
    mcf.add(N + i, t, c, 0);
    mcf.add(N * 2 + 0, N + i, 1e9, -(+x + y) + INF);
    mcf.add(N * 2 + 1, N + i, 1e9, -(+x - y) + INF);
    mcf.add(N * 2 + 2, N + i, 1e9, -(-x + y) + INF);
    mcf.add(N * 2 + 3, N + i, 1e9, -(-x - y) + INF);
  }
  ll ans = -mcf.run(s, t, sum) + INF*sum*2;
  write(ans);
  newline();
}

struct init {
  init() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} init_;



### Prompt

Please create a solution in CPP 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;

namespace {
  ll read() {
    ll x;
    cin >> x;
    return x;
  }

  string reads() {
    string s;
    cin >> s;
    return s;
  }

  template<class T>
  void write(T x) {
    cout << x << ' ';
  }

  void newline() {
    cout << '\n';
  }
}

struct mincostflow {
  struct edge {
    int v;
    long long c;
    long long w;
    int r;
  };

  vector<vector<edge>> G;

  mincostflow(int n) : G(n) {}

  void add(int u, int v, long long c, long long w) {
    int i = G[u].size();
    int j = G[v].size();
    G[u].push_back({v, c, w, j});
    G[v].push_back({u, 0, -w, i});
  }

  long long run(int s, int t, long long f) {
    const int N = G.size();
    long long res = 0;
    vector<long long> H(N);
    vector<long long> D(N);
    const long long INF = 1e18;
    vector<int> PE(N), PV(N);
    while (f > 0) {
      priority_queue<pair<long long, int>> q;
      fill(D.begin(), D.end(), INF);
      D[s] = 0;
      q.emplace(0, s);
      while (!q.empty()) {
        long long d = -q.top().first;
        int u = q.top().second;
        q.pop();
        if (D[u] < d) continue;
        for (int i = 0; i < G[u].size(); i++) {
          edge e = G[u][i];
          if (e.c > 0 && D[e.v] > D[u] + e.w + H[u] - H[e.v]) {
            D[e.v] = D[u] + e.w + H[u] - H[e.v];
            q.emplace(-D[e.v], e.v);
            PV[e.v] = u;
            PE[e.v] = i;
          }
        }
      }
      if (D[t] == INF) return -1;
      for (int i = 0; i < N; i++) H[i] += D[i];
      long long d = f;
      for (int i = t; i != s; i = PV[i]) {
        d = min(d, G[PV[i]][PE[i]].c);
      }
      f -= d;
      res += d * H[t];
      for (int i = t; i != s; i = PV[i]) {
        edge &e = G[PV[i]][PE[i]];
        e.c -= d;
        G[i][e.r].c += d;
      }
    }
    return res;
  }
};

int main() {
  int N = read();
  mincostflow mcf(N * 2 + 6);
  int s = N * 2 + 4;
  int t = N * 2 + 5;
  const ll INF = 1e10;
  int sum = 0;
  for (int i = 0; i < N; i++) {
    ll x = read(), y = read(), c = read();
    sum += c;
    mcf.add(s, i, c, 0);
    mcf.add(i, N * 2 + 0, 1e9, +x + y + INF);
    mcf.add(i, N * 2 + 1, 1e9, +x - y + INF);
    mcf.add(i, N * 2 + 2, 1e9, -x + y + INF);
    mcf.add(i, N * 2 + 3, 1e9, -x - y + INF);
  }
  for (int i = 0; i < N; i++) {
    ll x = read(), y = read(), c = read();
    mcf.add(N + i, t, c, 0);
    mcf.add(N * 2 + 0, N + i, 1e9, -(+x + y) + INF);
    mcf.add(N * 2 + 1, N + i, 1e9, -(+x - y) + INF);
    mcf.add(N * 2 + 2, N + i, 1e9, -(-x + y) + INF);
    mcf.add(N * 2 + 3, N + i, 1e9, -(-x - y) + INF);
  }
  ll ans = -mcf.run(s, t, sum) + INF*sum*2;
  write(ans);
  newline();
}

struct init {
  init() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} init_;



```