Monocarp and a Strategic Game
Contest: Educational Codeforces Round 150 (Rated for Div. 2)
Difficulty rating: 2700
Tags: geometry, sortings, two pointers

Monocarp plays a strategic computer game in which he develops a city. The city is inhabited by creatures of four different races — humans, elves, orcs, and dwarves.

Each inhabitant of the city has a happiness value, which is an integer. It depends on how many creatures of different races inhabit the city. Specifically, the happiness of each inhabitant is $$$0$$$ by default; it increases by $$$1$$$ for each other creature of the same race and decreases by $$$1$$$ for each creature of a hostile race. Humans are hostile to orcs (and vice versa), and elves are hostile to dwarves (and vice versa).

At the beginning of the game, Monocarp's city is not inhabited by anyone. During the game, $$$n$$$ groups of creatures will come to his city, wishing to settle there. The $$$i$$$-th group consists of $$$a_i$$$ humans, $$$b_i$$$ orcs, $$$c_i$$$ elves, and $$$d_i$$$ dwarves. Each time, Monocarp can either accept the entire group of creatures into the city, or reject the entire group.

The game calculates Monocarp's score according to the following formula: $$$m + k$$$, where $$$m$$$ is the number of inhabitants in the city, and $$$k$$$ is the sum of the happiness values of all creatures in the city.

Help Monocarp earn the maximum possible number of points by the end of the game!

Input format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^{5}$$$) — the number of groups of creatures that come to Monocarp's city.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$0 \leq a_i, b_i, c_i, d_i \leq 10^{9}$$$) — the number of humans, orcs, elves and dwarves (respectively) in the $$$i$$$-th group.

Output format:
Output a single number — the maximum score Monocarp can have by the end of the game. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$. That is, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then the solution will be accepted if $$$\frac{|a-b|}{\max(1,|b|)} \le 10^{-9}$$$.

Note that the correct answer is always an integer, but sometimes it doesn't fit in $$$64$$$-bit integer types, so you are allowed to print it as a non-integer number.

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

Note:
In the first example, the best course of action is to accept all of the groups.

In the second example, the best course of action is to accept the groups $$$2$$$ and $$$3$$$, and decline the groups $$$1$$$ and $$$4$$$.

Example input:
5
0 0 1 0
1 3 4 2
2 5 1 2
4 5 4 3
1 4 4 5

Example output:
85

Example input:
4
3 3 1 5
5 1 5 3
4 4 4 1
1 3 4 4

Example output:
41

Editorial:
Let's denote $$$a, b, c, d$$$ as the total number of humans, orcs, elves, and dwarves taken respectively. We calculate the contribution of humans and orcs to the final score. It will be $$$a(a-1) + b(b-1) - 2ab + a + b$$$, where $$$a(a-1) + b(b-1)$$$ is the contribution to the total happiness (and thus to the final score) for an increase of $$$1$$$ happiness point per inhabitant of the same race, $$$-2ab$$$ is the contribution to the total happiness decrease by $$$1$$$ point for each inhabitant of the hostile race, and the last two terms $$$a + b$$$ is the total number of humans and orcs, which contributes to the total score. Notice that $$$a(a-1) + b(b-1) - 2ab + a + b = (a-b)^2$$$.
Similarly for the contribution of elves and dwarves. So we need to maximize the expression $$$(a-b)^2+(c-d)^2$$$. Let's say we have $$$n$$$ vectors, the $$$i$$$-th of which is equal to $$$(x_i; y_i) = (a_i - b_i; c_i - d_i)$$$. Then note that we want to select some subset of vectors among the $$$n$$$ vectors $$$(x_i; y_i)$$$, a subset $$$A$$$ such that the value of the function $$$x^2+y^2$$$ is maximum for the vector $$$(x, y)$$$ equal to the sum of the vectors of subset $$$A$$$.
For each subset of vectors, we get a vector equal to the sum of the elements of the subset (vectors), let's denote the set of all such vectors as $$$S$$$.
Then consider the $$$n$$$ line segments at the vertices $$$(0; 0)$$$ and $$$(x_i; y_i)$$$ and calculate their Minkowski sum. We get a convex polygon. Notice that all elements of $$$S$$$ are in it by the definition of the Minkowski sum. Also, each vertex of the resulting convex polygon is in $$$S$$$, which is also known from the properties of the sum. Note that due to the upward convexity of the function we want to maximize, it is enough for us to only consider the vertices of the resulting polygon, not all vectors from $$$S$$$.
Thus, using a standard algorithm for calculating the Minkowski sum, we obtain the polygon of interest and calculate the values of the function at its vertices. We take the maximum from them. The total asymptotic time complexity is $$$O(n\ln{n})$$$.