Family Photos
Contest: Canada Cup 2016
Difficulty rating: 2900
Tags: games, greedy

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 format:
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 format:
Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
12 3 4 7
1 15 9 1

Example output:
1

Example input:
2
5 4 8 8
4 12 14 0

Example output:
4

Editorial:
1. We are going to transform the stacks in such a way that every move is no worse than passing.
2. Consider a stack with values a, b, c, d. (The top photo is worth a for Alice and b for Bonnie and the bottom photo is worth c for Alice and d for Bonnie.) If a + b ≥ c + d then taking the top photo is no worse than passing. We can prove it by rearranging the inequality: a - d ≥ c - b. a - d is the value of the stack, from Alice's perspective, if Alice gets to move first. c - b is the value, from Alice's perspective, if Bonnie gets to move first. So Alice doesn't incur a loss by making the first move, which means that a move here is no worse than passing. By symmetry, the same argument applies to Bonnie.
3. If a + b < c + d then both players would rather have the other player make the first move. However, this doesn't necessarily mean that the stack will be ignored by the players. If a > d then Alice can still profit by making the first move here. Since it would be even better for Alice if Bonnie made the first move, Alice can ignore this stack until Bonnie passes, and only then make a move here. So if a > d then this stack is equivalent to a single photo with value (a - d, d - a).
4. Likewise, if b > c then the stack is equivalent to a single photo with value (c - b, b - c).
5. If a + b < c + d and neither (3) nor (4) apply, both players will ignore the stack and we can simply delete it.
6. Now every move is no worse than passing, so every photo will eventually be taken. For every photo (a, b), replace it with a photo $$( \frac { a + b } { 2 }, \frac { a + b } { 2 } )$$ and add $${ \frac { a - b } { 2 } }$$ to the final answer. This is equivalent to the original problem because $$\frac{a-b}{2}+\frac{a+b}{2}=a$$ and $$\frac{a-b}{2} - \frac{a+b}{2} = -b$$.
7. Now every photo is worth the same to both players, so we can sort them in descending order and assign the photos with even indices to Alice and the photos with odd indices to Bonnie. Since every stack in the transformed problem has a + b ≥ c + d, this guarantees that the top photo will be taken before the bottom photo in each stack. The complexity is $$O(n \log n)$$.
8. Actually, this approach can be extended to solve the problem when each stack has any number of photos. The code linked below solves this more general problem. This problem wasn't asked in the contest because it was too similar to http://main.edu.pl/en/archive/pa/2010/ter. You can find the solution for this problem at http://www.mimuw.edu.pl/ idziaszek/termity/termity.pdf.
Code: http://codeforces.com/contest/725/submission/21731928