F. Forever in love
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$n$$$ trapezoids, all of height $$$1$$$.

Trapezoid $$$i$$$ is described by four positive integers $$$l_{i,0}$$$, $$$r_{i,0}$$$, $$$l_{i,1}$$$, $$$r_{i,1}$$$. At height $$$y = 0$$$, it occupies the interval $$$[-l_{i,0}, r_{i,0}]$$$. At height $$$y = 1$$$, it occupies the interval $$$[-l_{i,1}, r_{i,1}]$$$.

Equivalently, its vertices are $$$(-l_{i,0}, 0)$$$, $$$(r_{i,0}, 0)$$$, $$$(r_{i,1}, 1)$$$, $$$(-l_{i,1}, 1)$$$.

Before placing a trapezoid, you may reflect it with respect to the horizontal axis, the vertical axis, both, or neither.

The following picture shows the four possible orientations of the same trapezoid.

You have to place all trapezoids inside the strip $$$0 \le y \le 1$$$. You may translate each trapezoid only along the $$$x$$$ axis, and you may choose any left-to-right order.

The interiors of different trapezoids must not intersect, but they are allowed to touch at the boundary.

The width of a placement is $$$\max_x - \min_x$$$, where $$$\max_x$$$ is the largest $$$x$$$-coordinate covered by at least one trapezoid, and $$$\min_x$$$ is the smallest one.

Find the minimum possible width.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$).

Each of the next $$$n$$$ lines contains four integers $$$l_{i,0}$$$, $$$r_{i,0}$$$, $$$l_{i,1}$$$, $$$r_{i,1}$$$ ($$$1 \le l_{i,0}, r_{i,0}, l_{i,1}, r_{i,1} \le 10^9$$$).

For the given input format, it can be proved that the answer is always an integer.

Output

Print one integer: the minimum possible width.

Examples
Input
3
1 8 8 1
4 4 4 4
8 1 1 8
Output
33
Input
5
2 9 9 2
8 3 1 10
3 8 10 1
5 5 5 5
1 7 6 2
Output
58
Note

In the first sample, one optimal placement uses the order $$$1, 3, 2$$$. In the picture below, the left panel shows the order $$$1, 2, 3$$$, while the right panel shows the order $$$1, 3, 2$$$.

The right panel has width $$$33$$$, so the answer is $$$33$$$.