مشخصات $n$‌چرخ دایره‌ای شکل داده شده است. می‌دانیم دقیقا در حالی‌که دو چرخ با هم هیچ نقطه‌ی مشترکی نداشته باشند، می‌توان تسمه‌ای به دورشان انداخت و آن‌ها را به هم وصل کرد. می‌دانیم در بازار فقط تسمه‌هایی با طول صحیح پیدا می‌شود. تسمه نمی‌تواند خودش را قطع کند و اگر دو چرخ با تسمه‌ای به طول $L$ به هم وصل شوند با تسمه‌های بلند‌تر هم به هم وصل می‌شوند. می‌خواهیم طوری چرخ‌ها را به هم وصل کنیم که همه‌ی چرخ‌ها به هم وصل شوند و طول بزرگ‌ترین تسمه‌ای که خریداری می‌شود کمینه باشد.

در خط اول فایل ورودی عدد $n$‌($1 \leq n \leq 10^4$) آمده و در $n$ خط بعد در هر خط سه عدد $x_i$ و $y_i$ و $r_i$ آمده. که $(x_i,y_i)$ مختصات مرکز چرخ و $r_i$ شعاع چرخ $i$ است.

در فایل خروجی کمینه‌ی مقدار طول بزرگ‌ترین تسمه‌ای که خریداری می‌شود را بنویسید. فرض کنید مسئله همیشه جواب دارد

• محدودیت زمان: ۳۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل