Во оваа задача ќе разгледаме еден експеримент за пропагација.

Дадена е рамнина, на која во одредени точки постојат продуктори на одреден материјал. За поедноставно, ќе претпоставиме дека точките продуцираат некаква жица која рамномерно расте во тек на времето и за 1 час се продуцира должина 1.

Точките може да се активни (продуцираат жица) или заспани (не продуцираат). Една заспана точка (T2) може да се активира на тој начин што со веќе продуцирана жица од друга активна точка (Т1) ќе се поврзе со неа (ќе се воспостави врска со поставување на продуцираната жица, од страна на Т1, меѓу Т1 и Т2).

Поконкретно, замислете дека Т1 е активна точка. Таа почнува да продуцира жица во почетниот момент. Нека заспаната точка Т2 е на растојание R од Т1. После точно R часови, во Т1 има продуцирано жица со должина R. Од тој момент натаму, без загуба на никакво време за поставување, дел од веќе продуцираната жица во Т1 (со должина R) може да се постави меѓу Т1 и Т2 и со тоа да се активира и Т2. Во моментот по активацијата на Т2 и двете точки се активни и двете продолжуваат со продукција на жица, при што во Т1 ќе има жица колку што имало претходно но намалено за R, а во Т2 должината на жицата е 0.

Нека ги знаете позициите на N точки на рамнината (дадени по редослед од прва до N-та). Нека знаете дека во моментот на почеток на експериментот само првата точка е активна и тогаш почнува да продуцира жица. Пресметајте колку најмалку време е потребно за да се активираат сите точки според горе опишаниот начин.

Влез

Во првата линија е запишан еден цел број N (1 <= N <= 10), кој го означува бројот на точки. Во секој од следните N редови се запишани по два цели броја Xi, Yi (-1 000 000 000 <= Xi, Yi <= 1 000 000 000), кои ја означуваат позицијата на i-тата точка. Точките се означени со броевите од 1 до N. Не постојат две точки кои се наоѓаат на иста позиција.

Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 5.

Излез

Отпечатете го бараното минимално време за активација на сите точки. Бидејќи се работи за децимален број, отпечатете го истиот со најмалку 6 децимални места (види пример подолу).

P.S. Растојанието помеѓу две точки со координати (X₁, Y₁) и (X₂, Y₂) се пресметува според формулата: D = sqrt((X₂-X₁)² + (Y₂-Y₁)²), каде sqrt е функција за пресметување на квадратен корен (т.н. Евклидово растојание).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
3 1
2 1
4 1
5 1
6 2

излез
3.414214

Објаснување за првиот пример: По еден час, должината на жицата во точката 1 ќе биде еднаква на 1. Растојанието од точката 1 до точката 3 е еднакво на 1 (R=1), па можно е жица со должина 1, да се постави од точката 1 кон точката 3. Сега се активни 1 и 3, во двете точки ќе продолжи (или почне) да се продуцира жица, која и на двете места има должина 0 (таа што била веќе продуцирана во точката 1 е истрошена за поврзувањето со 3).

По еден час од ова, жицата продуцирана во точката 1 има должина 1, па можно е да се активира точката 2 (растојанието е точно 1). Слично, жицата продуцирана во точката 3 има должина 1, па можно е да се активира точката 4 (растојанието од точката 3 до точката 4 е точно 1). По ова, активни се точките 1, 2, 3 и 4.

По 1.414214 часа, должината на жицата во точката 4 ќе достигне 1.414214, па можно е да се активира и точката 5 (растојанието помеѓу точките 4 и 5 е 1.414214).

Вкупно, потребно е време од 3.414214 часа.