beecrowd | 1844

The Deathly Hallows

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 2

The culture of the native peoples of Brazil is dying! While it is estimated that in the 15th century there were more than one thousand native peoples in Brazil, today only 215 people are in the record. Recently, fossil hallowed relics associated to an extinct native people have been discovered in the west of the state of Santa Catarina. The relics probably were the foundations of walls of buildings. The figure below illustrates some found relics representing each by a line segment.

Now, the Government wants to turn all the lands in which the relics are located into an environmental preservation area. In order to make the work of the archaeologists easier, the Government will also build some trails, each one connecting two relics. The intention is to build as least as possible of trail, so that the environmental impact be the least as possible, but so that there is a path between any two trails. The figure below illustrates a manner of building trails between the relics of the figure above in order to minimise the total sum of the lengths of the trails.

Input

The first line of the input consists of a single integer N (1 ≤ N ≤ 103), which represents the number of relics found. Each one of the N following lines describe a relic by four integers, xA, yA, xB and yB (0 ≤ xA, yA, xB, yB ≤ 104), which represent the coordinates of the endpoints (xA, yA) and (xB, yB) of the line segment, with length not necessarily positive, that represents the trail.

Output

Print a line consisting of a single value which represents the optimal total sum of the lengths of the trails that connect the relics. As the company hired to build the trails charges for integer unity of built trail, if the value is not integer then round it up.

Input Samples Output Samples

7
0 0 3 2
1 12 1 17
9 4 7 7
13 1 18 1
16 14 13 11
16 20 21 15
16 19 21 19

31

7
0 0 0 2
0 4 0 6
2 6 4 6
6 6 8 6
8 4 8 2
8 0 6 0
4 0 2 0

12