Given a list of rectangles, compute the minimum perimeter of a polygon with axis-aligned sides such that the first rectangle is contained within the polygon and no point on the perimeter of the polygon lies inside, but not on the perimeter, of any of the rectangles.
Constraints
For any rectangle, and .
For at most 30% of marks, .
Input Specification
The first line will contain a single integer, .
The next lines each contain four integers, , , , and , defining the vertices of one of the rectangles.
Note that the second line of input corresponds to the rectangle that must be contained within the polygon.
Output Specification
Output the desired perimeter of the polygon.
Sample Input
4
8 4 13 8
2 1 6 7
4 7 9 11
14 7 19 11
Sample Output
32
Comments