Welcome to ZOJ
67 - ZOJ Monthly, June 2008 - 1005
Line Plotter

Time Limit: 5 Seconds      Memory Limit: 32768 KB

On a plotter, the mechanical arm that draws on paper with a pen has a motor that can move it back and forth across the paper sideways. The plotter also has a paper motor, which can move the paper orthogonally to the plotter's arm, which effectively is like moving the pen up and down the paper. The paper is square, and is oriented so its lower edge is parallel to the arm. This allows the plotter to move to any coordinates using the two motors. Both motors can be active simultaneously, and each motor can move the pen up to one pixel per millisecond in relation to the paper (it's possible for a motor to run slower).

Given the list of lines that the plotter must put on the paper, you should output the minimum time it takes to plot the given lines, in milliseconds. The plotter's pen starts at the coordinates (0,0), and after drawing all the lines, must return to (0,0). Note that the plotter cannot draw partial lines. Each element of lines will be in the form "x1 y1 x2 y2". This represents a line from point (x1,y1) to point (x2,y2). It takes 0 time to lower the pen down on the paper, and to raise it off the paper.


There are multiple test cases. For each test case, on the first line, there is a number n (1<=n<=15) indicating the number of lines. Following by n lines. On each line there are four integers indicating x1 y1 x2 y2 (0<=x1,y1,x2,y2<=9999). You may safely assume that no two lines can intersect at more than one point.


For each test case, output one integer indicating the minimum time it takes to plot the given lines in a line.

Sample Input

0 1 1 0
0 0 5 5
5 5 0 5
0 100 0 4

Sample Output


Submit    Status