Nước JOI sắp bầu tổng thống. Có \(n\) thành phố \(S_1,\ldots,S_n\). Thành phố \(S_i\) ở tọa độ \((x_i,y_i)\) có \(p_i\) cử tri. Các thành phố có tọa độ đôi một khác nhau. Khoảng cách giữa \(S_i\) và \(S_j\) là

Bạn là người quản lý lịch vận động tranh cử của ứng viên A. Chiến dịch kéo dài \(m\) ngày, mỗi ngày A diễn thuyết tại một thành phố. Nếu A diễn thuyết ở một thành phố, mọi cử tri tại thành phố đó và tại tất cả các thành phố cách đó không quá \(d\) đều chắc chắn bỏ phiếu cho A.

Hãy chọn \(m\) thành phố khác nhau để tổ chức diễn thuyết sao cho tổng số cử tri chắc chắn bỏ phiếu cho A càng lớn càng tốt. Một cử tri chỉ được tính một lần dù thành phố của họ nằm trong phạm vi ảnh hưởng của nhiều buổi diễn thuyết.

Đây là bài chỉ nộp kết quả, được chấm điểm tương đối.

Dữ liệu vào

Có năm tệp dữ liệu election-in1, election-in2, election-in3, election-in4, election-in5.

Trong mỗi tệp, dòng đầu chứa \(n\) (\(1 \le n \le 10000\)); dòng thứ hai chứa \(m\) (\(1 \le m \le 1000\), \(m \le n\)); dòng thứ ba chứa \(d\) (\(1 \le d \le 5000\)).

\(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i,y_i,p_i\), với \(0 \le x_i,y_i \le 5000\), \(1 \le p_i \le 10000\).

Dữ liệu ra

Nộp năm tệp election-out1, ..., election-out5, trong đó election-outk ứng với election-ink.

Mỗi tệp có \(m+1\) dòng. \(m\) dòng đầu, mỗi dòng chứa số thứ tự một thành phố được chọn, từ \(1\) đến \(n\). Thứ tự không quan trọng, nhưng các số không được trùng nhau. Dòng cuối chứa tổng số cử tri sống tại các thành phố cách ít nhất một thành phố được chọn không quá \(d\).

Chỉ nộp các tệp kết quả. Bạn có thể tạo kết quả bằng chương trình hoặc bằng cách khác, có thể chỉnh sửa kết quả bằng trình soạn thảo văn bản, và có thể dùng chương trình khác nhau cho từng tệp dữ liệu.

Chấm điểm

Có năm bộ dữ liệu, mỗi bộ tối đa \(20\) điểm; tổng cộng \(100\) điểm.

Để định nghĩa mốc chấm điểm \(T_{\mathrm{model}}\), thực hiện quy trình sau trên tập thành phố còn lại: tính số cử tri trong hình tròn bán kính \(d\) quanh mỗi thành phố, chọn thành phố có tổng lớn nhất (nếu hòa, chọn số thứ tự nhỏ nhất), rồi loại khỏi tập mọi thành phố cách thành phố đã chọn không quá \(d\). Lặp lại tối đa \(m\) lần. \(T_{\mathrm{model}}\) là tổng số cử tri được bao phủ bởi các thành phố chọn theo quy trình này. Nếu đã loại hết các thành phố, toàn bộ cử tri đều được bao phủ. Quy trình xác định mốc này không nhất thiết cho giá trị tối ưu.

Gọi \(T\) là tổng số cử tri được bao phủ trong kết quả bạn nộp, và \(T_{\max}\) là tổng lớn nhất trong tất cả kết quả được nộp cho bộ dữ liệu đó.

• Không nộp hoặc kết quả không hợp lệ: \(0\) điểm.
• Nếu \(T < T_{\mathrm{model}}\): \(0\) điểm.
• Nếu \(T \ge T_{\mathrm{model}}\) và \(T_{\max}=T_{\mathrm{model}}\) (không ai vượt mốc), nhận \(20\%\) số điểm của bộ dữ liệu.
• Nếu \(T \ge T_{\mathrm{model}}\) và \(T_{\max}>T_{\mathrm{model}}\), nhận tỉ lệ phần trăm số điểm của bộ dữ liệu bằng

Ví dụ

15
3
4
4 2 22
1 2 58
7 6 27
2 3 28
8 7 57
9 9 96
5 0 46
3 8 72
9 2 52
9 6 53
2 7 17
0 3 53
4 8 70
4 1 4
5 6 52

2
8
10
661