P15516 [BalticOI 2007] Building a Fence (Day 2)

Leopold is indeed a lucky fellow. He just won a huge estate in the lottery. The estate contains several grand buildings in addition to the main mansion, in which he intends to live from now on. However, the estate lacks a fence protecting the premises from trespassers, which concerns Leopold to a great extent. He wants to build a fence and, in order to save money, he decides it is sufficient to have a fence that encloses the main mansion, except for one important restriction: the fence must not lie too close to any of the buildings. To be precise, seen from above, each building is enclosed in a surrounding forbidden rectangle within which no part of the fence may lie. The rectangles’ sides are parallel to the $x$- and $y$-axis. Each part of the fence must also be parallel either to the $x$-axis or the $y$-axis. Help Leopold to compute the minimum length of any allowed fence enclosing the main mansion.  Figure 1: The main mansion (black) and three other buildings with surrounding forbidden rectangles. The thick black line shows a shortest allowed fence enclosing the main mansion.

The first line of the input contains a positive integer $m$ ($1 \leq m \leq 100$), the number of buildings on the estate. Then follow $m$ lines each describing a forbidden rectangle enclosing a building. Each row contains four space-separated integers $tx$, $ty$, $bx$, and $by$, where $(tx, ty)$ are the coordinates of the upper left corner and $(bx, by)$ are the coordinates of the bottom right corner of the rectangle. All coordinates obey $0 \leq tx < bx \leq 10,000$ and $0 \leq ty < by \leq 10,000$. The first rectangle is the forbidden rectangle enclosing the main mansion.

The output contains one line with a single positive integer equal to the minimum length of any allowed fence enclosing the main mansion.

In $30\%$ of the test cases, $m \leq 10$ holds.