You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

由于缺少降雨，农民约翰想要建造一个灌溉系统，以便在他的N块田地（1 <= N <= 2000）之间输送水。

每块田地i都由二维平面上一个不同的点 (xi, yi) 来表示，其中0 <= xi, yi <= 1000。在两块田地i和j之间建造一根水管的成本等于它们之间欧几里得距离的平方：

((x_i - x_j)^2 + (y_i - y_j)^2)

约翰想要建造一个成本最低的水管系统，以便将他所有的田地连接起来——这样一来，任何一块田地里的水都可以通过一系列水管到达其他任何一块田地。

不幸的是，帮助约翰安装灌溉系统的承包商拒绝安装任何一根水管，除非其成本（欧几里得长度的平方）至少为C（1 <= C <= 1000000）。

请帮助约翰计算出他将所有田地用一个水管网络连接起来所需支付的最小费用。

输入格式

• 第一行包含两个整数N和C，分别表示田地的数量和水管成本的下限。
• 接下来N行，每行包含两个整数xi和yi，表示第i块田地的坐标。

输出格式

输出一个整数，表示将所有田地连接起来所需支付的最小费用。如果无法将所有田地连接起来，则输出 -1。

输入输出样例 #1

输入 #1

3 11
0 2
5 0
4 3

输出 #1

46

样例解释

输入详情：

有 3 块田地，分别位于(0, 2)、(5, 0)和(4, 3)的位置。承包商只会安装成本至少为 11 的水管。

输出详情：

约翰不能在位于(4, 3)和(5, 0)的田地之间建造水管，因为其成本仅为 10。因此，他在(0, 2)和(5, 0)的田地之间建造了一根成本为 29 的水管，以及在(0, 2)和(4, 3)的田地之间建造了一根成本为 17 的水管。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le x_i,y_i \le 1000$，$1 \le c \le 10^6$。