Quốc gia JOI sắp bắt đầu phát sóng truyền hình. Trong nước có \(N\) ngôi nhà, và cần xây các tháp phát sóng để mọi ngôi nhà đều xem được truyền hình.

Nhà vua quyết định xây đúng \(K\) tháp. Nếu tháp thứ \(i\) được đặt tại tọa độ \((X_i,Y_i)\) và có mức công suất \(E_i\), mọi ngôi nhà cách tháp không quá \(\sqrt{E_i}\) đều nhận được tín hiệu của tháp đó. Khoảng cách giữa hai điểm \((a,b)\) và \((c,d)\) là

Tháp có mức công suất \(E_i\) tiêu thụ \(E_i\) đơn vị năng lượng. Mục tiêu là phủ sóng tất cả các ngôi nhà và làm tổng năng lượng tiêu thụ của \(K\) tháp nhỏ nhất có thể. Được phép xây tháp ngay tại vị trí của một ngôi nhà và đặt nhiều tháp tại cùng một tọa độ.

Yêu cầu

Đây là bài chỉ nộp kết quả (output-only). Bạn được cung cấp các bộ dữ liệu chứa tọa độ các ngôi nhà và số tháp cần xây. Với mỗi bộ dữ liệu, hãy tạo và nộp kết quả mô tả vị trí, mức công suất của các tháp. Năng lượng tiêu thụ càng ít thì điểm càng cao.

Dữ liệu vào

Có \(5\) bộ dữ liệu được cung cấp trong tệp đính kèm của bài toán. Các tệp dữ liệu vào là:

• 01.txt: \(N=200\), \(K=20\).
• 02.txt: \(N=500\), \(K=10\).
• 03.txt: \(N=500\), \(K=20\).
• 04.txt: \(N=500\), \(K=15\).
• 05.txt: \(N=500\), \(K=30\).

Mỗi tệp đầu vào có định dạng:

• Dòng đầu chứa hai số nguyên \(N,K\) cách nhau bởi dấu cách, lần lượt là số ngôi nhà và số tháp cần xây.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) cách nhau bởi dấu cách, là tọa độ ngôi nhà thứ \(i\).

Không có hai ngôi nhà trùng tọa độ.

Dữ liệu ra

Với mỗi bộ dữ liệu, chuẩn bị một kết quả gồm đúng \(K\) dòng. Dòng thứ \(i\) (\(1\le i\le K\)) chứa ba số nguyên \(X_i,Y_i,E_i\) cách nhau bởi dấu cách, mô tả tọa độ và mức công suất của tháp thứ \(i\).

Kết quả hợp lệ phải tuân thủ các giới hạn bên dưới và phủ sóng tất cả các ngôi nhà. Cụ thể, với mỗi ngôi nhà thứ \(j\), phải tồn tại ít nhất một tháp thứ \(i\) sao cho

Ràng buộc

• \(1\le N\le500\).
• \(1\le K\le30\).
• \(0\le A_i,B_i\le1\,000\,000\) với \(1\le i\le N\).
• \(0\le X_i,Y_i\le1\,000\,000\) với \(1\le i\le K\).
• \(0\le E_i\le1\,000\,000\,000\,000=10^{12}\) với \(1\le i\le K\).
• Tất cả các giá trị trong tệp đầu vào và kết quả đều phải là số nguyên.

Cách nộp bài

Nộp kết quả tương ứng với từng bộ dữ liệu đầu vào. Khi nộp, hệ thống kiểm tra kết quả có khớp với định dạng quy định trong phần Dữ liệu ra hay không; phản hồi lúc nộp chỉ là kiểm tra định dạng. Thí sinh không cần nộp chương trình tạo kết quả.

Chấm điểm

Mỗi bộ dữ liệu có tối đa \(20\) điểm; tổng điểm của \(5\) bộ dữ liệu là \(100\) điểm. Điểm cho từng bộ dữ liệu được tính riêng như sau.

Gọi \(E_0\) là tổng năng lượng tiêu thụ nhỏ nhất trong các kết quả do các thí sinh nộp cho bộ dữ liệu đó. Nếu kết quả của bạn không thỏa mãn các điều kiện của bài toán, bạn nhận \(0\) điểm cho bộ dữ liệu này. Nếu kết quả hợp lệ, gọi tổng năng lượng tiêu thụ của bạn là

• Nếu \(E/E_0>1.5\), bạn nhận \(0\) điểm.
• Nếu \(E/E_0\le1.5\), điểm của bạn là giá trị sau được làm tròn đến số nguyên gần nhất, xét chữ số đầu tiên sau dấu thập phân (từ \(5\) trở lên thì làm tròn lên):

Ví dụ

10 3
0 300000
500000 800000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0

200000 700000 160000000000
300000 300000 90000000000
750000 0 62500000000