题目描述
珅泽教育准备升级校园网络,把分布在不同位置的若干场馆用光缆连接起来,使任意两个场馆之间都能通过光缆网络互相通信。每个场馆用平面上的一个点表示,两点之间铺设光缆的费用等于它们欧几里得距离的平方。
由于过短的线路无法满足施工规范,施工方只允许铺设费用不少于门槛 的连接。刘老师希望在符合要求的连接中选择若干条,使全部场馆连通且总费用最低。请输出最低总费用;如果无论怎样选择都无法连通全部场馆,则输出 。
输入格式
第一行输入 ,随后 行输入坐标 。
输出格式
输出最低费用;无法连通输出 。
输入 #1
3 11
0 2
5 0
4 3
输出 #1
46
输入 #2
2 1
0 0
1 0
输出 #2
1
输入 #3
3 1000
0 0
1 1
2 2
输出 #3
-1
数据范围与约定
- 2 ≤ ≤ 60
- 0 ≤ , ≤ 1000
- 1 ≤ ≤ 1000000