\(N\) корів (\(1 \leq N \leq 10^5\)) Фермера Джона розмістилися на його фермі та хочуть побудувати комунікаційну мережу для обміну електронними текстовими повідомленнями.

\(i\)-а корова розміщена в точці \((x_i,y_i)\), де \(0 \leq x_i \leq 10^6\) \(0 \leq y_i \leq 10\).

Вартість побудови комунікаційної лінії між коровами \(i\) та \(j\) є квадрат відстані між ними: \((x_i-x_j)^2 + (y_i-y_j)^2\).

Обчисліть мінімальну вартість побудови комунікаційної мережі, так щоб кожна корова могла розмовляти з будь-якою іншою безпосередньо або через послідовність ліній зв'язку.

Примітка : Лімітний час на тест = 4s, у два рази більше звичайного..

Формат вхідних даних

Перший рядок введення містить \(N\), кожен з наступних \(N\) рядків описує \( x \) і \( y \) - координати корови, всі числа - цілі.

Формат вихідних даних

Виведіть мінімальну вартість мережі, яка дозволить комунікувати всім корів. Зауважимо, що вартість може бути дуже великою, і може вимагати 64-бітну цілу типу "long long" C++.

Приклад вхідних даних

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

Приклад вихідних даних

660

ОЦІНЮВАННЯ:

• У тестах 2-3 \(N \le 1000\).

• У тестах 4-15 немає додаткових обмежень.

  Автор: Brian Dean