Kết nối internet

Thành phố nơi Nam sinh sống đã xây dựng hệ thống Wi-Fi công cộng để phục vụ khách du lịch và người dân trong thành phố. Hệ thống bao gồm $n$ trạm phát sóng được đánh số từ $1$ đến $n$, trạm thứ $i$ được đặt ở vị trí tương ứng với tọa độ $(x_i,y_i)$ trên bản đồ mặt phẳng tọa độ của thành phố. Các trạm phát sóng này đều có mức độ phủ sóng là $s$. Hai trạm phát sóng $i$ và $j$ có thể truyền thông tin cho nhau bằng sóng nếu $|x_i-x_j|+|y_i-y_j|\le s$, hoặc trạm phát sóng $i$ có thể truyền thông tin qua một số trạm phát sóng trung gian để tới được trạm phát sóng $j$. Một nhóm các trạm phát sóng gọi là liên thông nếu như hai trạm bất kỳ trong nhóm có thể truyền thông tin cho nhau. Mỗi nhóm liên thông chỉ cần một đường truyền cung cấp internet để tất cả các trạm phát sóng này đều có thể phát được mạng internet cho người dân sử dụng.

Tuy nhiên, sau một thời gian sử dụng, chi phí duy trì hoạt động của hệ thống này là rất lớn, trong đó chi phí sử dụng mạng internet hàng tháng là chiếm nhiều nhất. Chi phí sử dụng mạng internet tỉ lệ thuận với số đường truyền cung cấp internet. Do đó, chính quyền thành phố muốn giảm thiểu số lượng đường truyền cung cấp internet mà vẫn bảo đảm tất cả các trạm đều có mạng internet bằng cách thiết kế các đường dây cáp kết nối trực tiếp một số trạm phát sóng với nhau. Với hai trạm phát sóng $u$ và $v$ chưa truyền được thông tin cho nhau, khi kết nối trực tiếp chúng bằng đường dây cáp, hai trạm phát sóng này có thể truyền tin cho nhau, vì vậy, nếu một trong hai trạm có mạng internet thì trạm còn lại cũng có mạng internet và toàn bộ nhóm liên thông chứa trạm này đều phát được mạng internet, do đó, có thể giảm đi một đường truyền cung cấp internet. Chi phí để kết nối hai trạm phát sóng $u$ và $v$ bằng đường dây cáp là $|x_u-x_v|+|y_u-y_v|$. Chính quyền thành phố muốn xây dựng phương án giảm đi $k$ đường truyền cung cấp internet mà vẫn bảo đảm trạm phát sóng nào cũng có mạng internet bằng cách sử dụng thêm $k$ đường dây cáp kết nối trực tiếp sao cho tổng chi phí kết nối bằng dây cáp là nhỏ nhất.

Yêu cầu: Cho biết số lượng và vị trí của $n$ trạm phát sóng, mức độ phủ sóng $s$ của các trạm phát sóng và số lượng $k$ đường truyền cung cấp internet cần giảm đi, hãy tính chi phí nhỏ nhất để kết nối các trạm phát sóng bằng dây cáp sao cho trạm phát sóng nào cũng có mạng internet.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương $n,s,k$ $(n\le {10}^5$; $s\le {10}^9$; $k\le 20)$;
• Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa hai số nguyên không âm $x_i,y_i$ mô tả vị trí trạm phát sóng thứ $i$ $(1\le i\le n$; $x_i,y_i\le {10}^9)$.

Dữ liệu bảo đảm không có hai trạm phát sóng nào có tọa độ trùng nhau và số lượng đường truyền cung cấp internet cần sử dụng cho hệ thống ban đầu lớn hơn $k$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là chi phí nhỏ nhất để kết nối các trạm phát sóng thỏa mãn yêu cầu.

Ràng buộc

• $1\le n\le {10}^5$; $1\le s\le {10}^9$; $1\le k\le 20$.
• $0\le x_i,y_i\le {10}^9$; các trạm có tọa độ đôi một khác nhau.
• Số nhóm liên thông ban đầu lớn hơn $k$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 1000$.
• Subtask 2 ($20\%$ số điểm): tọa độ tất cả các trạm phát sóng đều nằm trên một đường thẳng.
• Subtask 3 ($20\%$ số điểm): giá trị tọa độ mỗi trạm phát sóng không vượt quá $1000$.
• Subtask 4 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ