Keke lives in the future and he has just bought a flying scooter! To accommodate for the costs of owning such a device he has set up a delivery service. Today Keke has received n requests numbered 1,2,\dots,n of the form: get package i from point (a_i, b_i) and deliver it to point (c_i, d_i). Keke's home lies at point (0, 0). Keke has extra anti-gravity devices that he can rope on to the packages, making the scooter's carrying capacity practically infinite. Now he is calculating the shortest possible path to deliver all the packages and return home.

Input

The first line contains a single integer n. The i-th of next n following lines contains four integer a_i, b_i, c_i, d_i.

Output

Print the length of the shortest possible path. The answer is considered correct if the absolute or relative error is less that 10^{-6}.

Constraints

• 1 \leq n \leq 10
• -10^9 \leq a_i, b_i, c_i, d_i \leq 10^9
• All input values are integers

Example 1

Input:

2
0 1 1 1
1 1 0 1

Output:

4

Example 2

Input:

3
-1 -1 -4 4 
-6 -5 -5 -10 
7 4 -8 0

Output:

49.16957315214831639866

Example 3

Input:

10
-836129193 -511793054 674862860 -315012357 
-58523359 553629643 -21638861 -338547620 
156411079 -433341685 76148004 -813719892 
-845271369 -99405035 -423531667 -965832764 
73489491 133366259 458635298 865736920 
726016447 -289528125 -181935146 -156162816 
-858402779 448113563 -381212035 443790339 
953337225 490421470 -541758442 -257028769 
-29071198 996146588 999749708 -436105637 
-946529318 612250680 289668989 -452619170

Output:

9294216739.04733216855674982071