#include <bits/stdc++.h>
using namespace std;
struct atom {
  long long x, y;
  void scan() { scanf("%I64d%I64d", &x, &y); }
} A[110000][2], B[210000];
int n, len;
long long ans = 0, C[210000];
void add(int k1, int k2) {
  atom k3;
  if (k1 <= n)
    k3 = A[k1][0];
  else
    k3 = A[k1 - n][1];
  if (k2 == 1)
    ans += k3.x;
  else
    ans -= k3.y;
}
int compare(atom k1, atom k2) {
  return k1.x > k2.x || (k1.x == k2.x && k1.y < k2.y);
}
int compare2(long long k1, long long k2) { return k1 > k2; }
void add2(int k1, int k2) {
  if (k2 == 1)
    ans += A[k1][0].x - A[k1][1].y;
  else
    ans -= A[k1][0].y - A[k1][1].x;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) A[i][0].scan(), A[i][1].scan();
  int pre = 0;
  for (int i = 1; i <= n; i++)
    if (A[i][0].x <= A[i][1].y && A[i][1].x >= A[i][0].y)
      continue;
    else {
      pre++;
      A[pre][0] = A[i][0];
      A[pre][1] = A[i][1];
    }
  n = pre;
  for (int i = 1; i <= n; i++) {
    if (A[i][0].x + A[i][0].y < A[i][1].x + A[i][1].y) continue;
    len++;
    B[len] = (atom){A[i][0].x + A[i][0].y, i};
    len++;
    B[len] = (atom){A[i][1].x + A[i][1].y, i + n};
  }
  sort(B + 1, B + len + 1, compare);
  for (int i = 1; i <= len; i++)
    if (i & 1)
      add(B[i].y, 1);
    else
      add(B[i].y, -1);
  int now = len & 1;
  len = 0;
  int k1 = 0, k2 = 0;
  for (int i = 1; i <= n; i++)
    if (A[i][0].x + A[i][0].y < A[i][1].x + A[i][1].y) {
      if (A[i][0].x > A[i][1].y && A[i][0].y <= A[i][1].x)
        ans += A[i][0].x - A[i][1].y, k1++;
      else if (A[i][0].y > A[i][1].x && A[i][0].x <= A[i][1].y)
        ans += A[i][1].x - A[i][0].y, k2++;
      else
        B[++len] = (atom){A[i][0].x + A[i][0].y - A[i][1].x - A[i][1].y, i};
    }
  sort(B + 1, B + len + 1, compare);
  if (len) cout << "fa" << endl;
  int k3 = 1;
  while (k3 <= len) {
    if (now == 1) {
      if (k1)
        k1--;
      else
        add2(B[k3].y, 1), k3++;
    } else if (k2)
      k2--;
    else
      add2(B[k3].y, -1), k3++;
    now ^= 1;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

Alice and Bonnie are sisters, but they don't like each other very much. So when some old family photos were found in the attic, they started to argue about who should receive which photos. In the end, they decided that they would take turns picking photos. Alice goes first.

There are n stacks of photos. Each stack contains exactly two photos. In each turn, a player may take only a photo from the top of one of the stacks.

Each photo is described by two non-negative integers a and b, indicating that it is worth a units of happiness to Alice and b units of happiness to Bonnie. Values of a and b might differ for different photos.

It's allowed to pass instead of taking a photo. The game ends when all photos are taken or both players pass consecutively.

The players don't act to maximize their own happiness. Instead, each player acts to maximize the amount by which her happiness exceeds her sister's. Assuming both players play optimal, find the difference between Alice's and Bonnie's happiness. That is, if there's a perfectly-played game such that Alice has x happiness and Bonnie has y happiness at the end, you should print x - y.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the number of two-photo stacks. Then follow n lines, each describing one of the stacks. A stack is described by four space-separated non-negative integers a1, b1, a2 and b2, each not exceeding 109. a1 and b1 describe the top photo in the stack, while a2 and b2 describe the bottom photo in the stack.

Output

Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

Examples

Input

2
12 3 4 7
1 15 9 1


Output

1


Input

2
5 4 8 8
4 12 14 0


Output

4


Input

1
0 10 0 10


Output

-10

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct atom {
  long long x, y;
  void scan() { scanf("%I64d%I64d", &x, &y); }
} A[110000][2], B[210000];
int n, len;
long long ans = 0, C[210000];
void add(int k1, int k2) {
  atom k3;
  if (k1 <= n)
    k3 = A[k1][0];
  else
    k3 = A[k1 - n][1];
  if (k2 == 1)
    ans += k3.x;
  else
    ans -= k3.y;
}
int compare(atom k1, atom k2) {
  return k1.x > k2.x || (k1.x == k2.x && k1.y < k2.y);
}
int compare2(long long k1, long long k2) { return k1 > k2; }
void add2(int k1, int k2) {
  if (k2 == 1)
    ans += A[k1][0].x - A[k1][1].y;
  else
    ans -= A[k1][0].y - A[k1][1].x;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) A[i][0].scan(), A[i][1].scan();
  int pre = 0;
  for (int i = 1; i <= n; i++)
    if (A[i][0].x <= A[i][1].y && A[i][1].x >= A[i][0].y)
      continue;
    else {
      pre++;
      A[pre][0] = A[i][0];
      A[pre][1] = A[i][1];
    }
  n = pre;
  for (int i = 1; i <= n; i++) {
    if (A[i][0].x + A[i][0].y < A[i][1].x + A[i][1].y) continue;
    len++;
    B[len] = (atom){A[i][0].x + A[i][0].y, i};
    len++;
    B[len] = (atom){A[i][1].x + A[i][1].y, i + n};
  }
  sort(B + 1, B + len + 1, compare);
  for (int i = 1; i <= len; i++)
    if (i & 1)
      add(B[i].y, 1);
    else
      add(B[i].y, -1);
  int now = len & 1;
  len = 0;
  int k1 = 0, k2 = 0;
  for (int i = 1; i <= n; i++)
    if (A[i][0].x + A[i][0].y < A[i][1].x + A[i][1].y) {
      if (A[i][0].x > A[i][1].y && A[i][0].y <= A[i][1].x)
        ans += A[i][0].x - A[i][1].y, k1++;
      else if (A[i][0].y > A[i][1].x && A[i][0].x <= A[i][1].y)
        ans += A[i][1].x - A[i][0].y, k2++;
      else
        B[++len] = (atom){A[i][0].x + A[i][0].y - A[i][1].x - A[i][1].y, i};
    }
  sort(B + 1, B + len + 1, compare);
  if (len) cout << "fa" << endl;
  int k3 = 1;
  while (k3 <= len) {
    if (now == 1) {
      if (k1)
        k1--;
      else
        add2(B[k3].y, 1), k3++;
    } else if (k2)
      k2--;
    else
      add2(B[k3].y, -1), k3++;
    now ^= 1;
  }
  cout << ans << endl;
  return 0;
}

```