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.
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.
Print one integer: the minimum possible width.
31 8 8 14 4 4 48 1 1 8
33
52 9 9 28 3 1 103 8 10 15 5 5 51 7 6 2
58
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$$$.
