SP7740 BOI7FEN - Fence

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 decides to build a fence, but unfortunately he cannot afford to put it round all of his newly acquired land. After some thinking, 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.  Figure 5.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 file contains a positive integer m (1

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