Водопровід-2#86

Водопровід-2

1 секунда
64 мегабайти
Середня

План міста містить котеджів, розташованих у точках з координатами (X_i, Y_i) для i = 1, \ldots, N. Яка мінімальна загальна довжина водопровідних труб потрібна, щоб з'єднати всі котеджів, безпосередньо або через інші котеджі?

Вхідні дані

Перший рядок містить одне ціле число (1 \leq N \leq 100) — кількість котеджів. Кожен з наступних рядків містить по два додатних цілих числа X_i і Y_i (1 \leq X_i, Y_i \leq 100), які задають координати котеджу.

Вихідні дані

Виведіть єдине ціле число — мінімальну загальну довжину водопровідних труб, необхідну для з'єднання всіх котеджів. Відповідь округліть до найближчого цілого.

Приклади

Приклад 1

Loading
Loading