Do thiếu mưa, Farmer John muốn xây dựng một hệ thống tưới tiêu để dẫn nước giữa \(N\) cánh đồng của mình (\(1 \le N \le 2\,000\)).

Mỗi cánh đồng \(i\) được mô tả bởi một điểm \((x_i,y_i)\) riêng biệt trên mặt phẳng hai chiều, với \(0 \le x_i,y_i \le 1\,000\). Chi phí xây dựng một đường ống dẫn nước giữa hai cánh đồng \(i\) và \(j\) bằng bình phương khoảng cách Euclid giữa chúng:

FJ muốn xây dựng một hệ thống đường ống có chi phí nhỏ nhất sao cho tất cả các cánh đồng đều được nối với nhau, tức là nước ở một cánh đồng bất kỳ có thể đi theo một dãy đường ống để đến bất kỳ cánh đồng nào khác.

Đáng tiếc, nhà thầu đang giúp FJ lắp đặt hệ thống tưới tiêu từ chối lắp bất kỳ đường ống nào có chi phí (bình phương độ dài Euclid) nhỏ hơn \(C\) (\(1 \le C \le 1\,000\,000\)).

Hãy giúp FJ tính số tiền nhỏ nhất cần trả để nối tất cả các cánh đồng bằng một mạng lưới đường ống.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\).

Ràng buộc

• \(1 \le N \le 2\,000\).
• \(0 \le x_i,y_i \le 1\,000\) và các điểm \((x_i,y_i)\) đôi một khác nhau.
• \(1 \le C \le 1\,000\,000\).

Dữ liệu ra

In ra chi phí nhỏ nhất của một mạng lưới đường ống nối tất cả các cánh đồng, hoặc \(-1\) nếu không thể xây dựng mạng lưới như vậy.

Ví dụ

3 11
0 2
5 0
4 3

46

Nguồn

USACO 2014 March Contest, Silver — Watering the Fields

Tác giả: Brian Dean, 2014.