Мережа доріг#1445
У маленькій, але дуже гордій країні є військових баз. Король вирішив з'єднати ці бази дорогами так, щоб можна було дістатися з будь-якої бази до будь-якої іншої, можливо, проходячи через кілька доріг. Цікавий факт про цю країну: інженери можуть будувати дороги лише з півночі на південь або з заходу на схід. Король доручив міністру транспорту розробити план, а той, у свою чергу, поклав це завдання на вас — Верховного Програміста держави. Вам потрібно визначити мінімальну сумарну довжину доріг у побудованій мережі.
У країні використовується декартова система координат: вісь спрямована із заходу на схід, а вісь — з півдня на північ. Розміри баз досить малі, щоб їх можна було вважати точками, а дороги — відрізками на площині.
Перший рядок містить кількість баз (1 \leq n \leq 10). Кожен з наступних рядків містить координати бази у форматі "", де — абсциса, а — ордината, і — цілі числа від до включно.
Виведіть одне число — мінімальну сумарну довжину всіх побудованих доріг, округлену рівно до знаків після коми за стандартними правилами округлення.
Приклад 1
Можливі оптимальні мережі доріг для наведених вище прикладів показано нижче:
