Bạn được cho một mạng lưới các tháp phát sóng không dây. Mỗi tháp có một phạm vi hoạt động và có thể gửi dữ liệu đến các tháp lân cận miễn là khoảng cách giữa chúng nhỏ hơn hoặc bằng phạm vi của tháp gửi.

Các tháp hiện đang sử dụng giao thức truyền thông cũ A, nhưng có một giao thức mới tốt hơn là B. Chúng ta đang cân nhắc nâng cấp một số tháp để gửi dữ liệu bằng giao thức B nhằm đạt được băng thông tốt hơn.

Có một ràng buộc quan trọng: nếu một tháp \(T\) đang sử dụng giao thức mới B, thì mọi tháp nằm trong phạm vi của \(T\) cũng phải đang chạy giao thức B để chúng có thể hiểu được dữ liệu gửi từ \(T\). Điều ngược lại là không cần thiết — các tháp chạy giao thức mới B vẫn có thể nhận dữ liệu từ các tháp sử dụng giao thức cũ A.

Nhiệm vụ của bạn là chọn ra tập hợp các tháp tốt nhất để nâng cấp từ giao thức A lên giao thức B. Mỗi tháp khi nâng cấp sẽ đem lại một số điểm nhất định, điểm này có thể dương hoặc âm (đại diện cho giá trị thu được trừ đi chi phí lắp đặt). Hãy chọn tập hợp các tháp cần nâng cấp sao cho tổng số điểm của các tháp được nâng cấp là lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ thử nghiệm, \(T\).
Mỗi bộ thử nghiệm bắt đầu bằng số lượng tháp, \(n\).
\(n\) dòng tiếp theo, mỗi dòng chứa 4 số nguyên: \(x, y, r, s\). Chúng mô tả một tháp tại tọa độ \((x, y)\), có phạm vi hoạt động là \(r\) và điểm số (giá trị của việc nâng cấp lên giao thức mới) là \(s\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất ra:

Case #X: score

Ràng buộc

• \(1 \le T \le 55\)
• \(-10\,000 \le x, y \le 10\,000\)
• \(1 \le r \le 20\,000\)
• \(-1000 \le s \le 1000\)
• Không có hai tháp nào có cùng tọa độ.

Phân nhóm

• Tập dữ liệu nhỏ: \(1 \le n \le 15\).
• Tập dữ liệu lớn: \(1 \le n \le 500\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

1
5
0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20

Case #1: 5

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Wi-fi Towers.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.