Keçi İpləri

Bir fermerin n keçisi var. Təsadüfən, onun həmçinin keçiləri otarmaq istədiyi sahədə n sabit dirəyi var. O, hər keçini bir dirəyə bir iplə bağlamaq istəyir. O, hər keçiyə mümkün qədər çox sərbəstlik vermək istəyir – lakin, keçi iplikləri dolaşmağa meyllidir, buna görə də heç bir keçinin başqa bir keçinin ərazisinə girməsinə icazə verə bilməz. O, mümkün qədər çox ipdən istifadə edə bilərmi?

Giriş verilənləri

Girişdə bir neçə test halı olacaq. Hər test halı sahədəki dirəklərin sayını göstərən n (2 ≤ n ≤ 50) tam ədədi ilə başlayacaq. Növbəti n sətirdə həmin sahədəki dirəyin kartes koordinatlarını (metrlə) göstərən bir cüt tam ədəd, x və y (0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000) olacaq. Heç bir iki dirək eyni mövqedə olmayacaq. Siz sahənin keçilərin heç vaxt sərhədinə çatmayacağı qədər böyük olduğunu qəbul edə bilərsiniz. Giriş bir 0 olan sətirlə bitəcək.

Çıxış verilənləri

Hər test halı üçün fermerin mümkün qədər çox istifadə edə biləcəyi ipin uzunluğunu, metrlə göstərən bir onluq ədəd çıxarın. Bu dəyəri dəqiq iki onluq yerə qədər yuvarlaqlaşdırılmış şəkildə çıxarın. Boşluq çıxarmayın və cavablar arasında boş sətir çıxarmayın.