В связи с недостатком дождей Фермер Джон хочет построить ирригационную систему для доставки воды на N его полей (1 <= N <= 2000).
Все поля описываются различными точками (xi,yi) на плоскости, где 0<=xi,yi<=1000. Цена постройки трубы для доставки воды из точки i в точку j равна квадрату евклидового расстояния между ними:
(xi - xj)^2 + (yi - yj)^2
ФД хочет проложить минимальную по стоимости систему труб так, чтобы все его поля были соединены таким образом, чтобы водя из любого поля могла достичь любого другого поля по некоторой последовательности из проложенных труб.
К несчастью, подрядчик, у которого ФД заказал эту систему, отказывается прокладывать трубы стоимостью меньше чем C (1 <= C <= 1,000,000).
Пожалуйста, помогите ФД определить минимальное количество денег, которые ФД должен заплатить, чтобы проложить задуманную систему труб.
PROBLEM NAME: irrigation
Формат входных данных
* Строка 1: Целые числа N и C.
* Строки 2..1+N: Строка i+1 содержит целые числа xi и yi.
Формат выходных данных
* Строка 1: Минимальная стоимость задуманной сети труб , или -1 если такая сеть не может быть построена.
Примечание
ФД не может построить трубу между полями в точках (4,3) и (5,0), поскольку её стоимость не более 10. Поэтому он построит трубы между (0,2) и (5,0) со стоимостью 29 и трубу между (0,2) и (4,3) со стоимостью 17.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 11
0 2
5 0
4 3
|
46
|