Electricity

Time limit1.5sMemory limit128 MB

Summary

Place a power plant at an integer intersection minimizing the sum over axis-aligned rectangles of the Manhattan distance to the nearest rectangle corner.

Level: Hard8 of 10
Topics: Geometry, Binary search, Divide and conquer
Solved: No attempts yet

Problem

In the 19th century, electricity was slowly coming into general use. One of the first large-scale uses of electricity was lighting public spaces. The company Edison Patents & Theft Inc. decided to show the New York city authorities how useful electricity is by lighting the more important streets of Manhattan. Manhattan has a very regular layout made up only of streets (parallel to the $X$ axis) and avenues (parallel to the $Y$ axis).

Because the technology is still in its infancy, lighting is installed one quarter at a time. A quarter is a rectangle whose sides lie on two streets and two avenues. Each quarter is given by two opposite corners of the rectangle, and these corners always lie on intersections of streets and avenues. Quarters may overlap. Each quarter is lit by one closed circuit. Because of technical limits, that circuit has only four break points, one at each corner of the quarter.

After deciding which quarters to light, the company wants to find the intersection where it is cheapest to build a power plant. The cost of the power plant is the sum of its distances to every quarter. The distance from the power plant to a quarter is the number of streets plus the number of avenues between the power plant and the nearest corner of that quarter, that is, the Manhattan distance between the two points. If the power plant is at $(p_x, p_y)$ , its distance to a corner $(v_x, v_y)$ is $|p_x - v_x| + |p_y - v_y|$ , and its distance to the quarter $(x_1, y_1, x_2, y_2)$ is the minimum of this value over the four corners $(x_1, y_1)$ , $(x_1, y_2)$ , $(x_2, y_1)$ , and $(x_2, y_2)$ . The power plant can be built at any intersection with integer coordinates. The figure shows one possible choice of quarters and a power plant location.

Use 21st-century technology to solve their problem: for the given quarters, find the minimum possible cost of the power plant.

Input

The first line contains $N$ $(1 \le N \le 200\,000)$ , the number of quarters.

Each of the next $N$ lines describes one quarter with four coordinates $x_1$ , $y_1$ , $x_2$ , and $y_2$ , where $x_1 < x_2$ and $y_1 < y_2$ . All coordinates are positive integers less than $10^7$ (ten million).

Output

Print one number on a single line: the minimum possible cost of the power plant.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
3
4 2 13 5
11 1 15 6
2 11 8 18
```
Expected output
```
11
```