와이파이 타워

무선 통신 탑의 네트워크가 주어진다. 각 탑에는 통신 범위가 있으며, 거리가 송신하는 탑의 통신 범위 이하인 경우 인접한 탑으로 데이터를 보낼 수 있다.

탑들은 오래된 통신 프로토콜 A를 사용하고 있지만, 새롭고 더 나은 프로토콜 B를 사용할 수 있다. 더 나은 대역폭을 얻기 위해 일부 탑을 프로토콜 B로 데이터를 보내도록 업그레이드하려 한다.

한 가지 중요한 제약이 있다. 탑 T가 새로운 프로토콜 B를 사용한다면, T의 통신 범위 안에 있는 모든 탑도 프로토콜 B를 사용해야 하며, 그래야 그 탑들이 T가 보낸 데이터를 이해할 수 있다. 그 역은 필요하지 않다. 즉, 새로운 프로토콜 B를 사용하는 탑은 오래된 프로토콜 A를 사용하는 탑으로부터 데이터를 받을 수 있다.

프로토콜 A에서 프로토콜 B로 업그레이드할 최적의 탑 집합을 선택해야 한다. 탑을 업그레이드하면 이득이 있지만 설치 비용도 든다. 따라서 각 탑에는 양수일 수도 있고 음수일 수도 있는 점수가 있으며, 이는 해당 탑을 업그레이드하는 가치를 나타낸다. 업그레이드한 탑들의 총점이 최대가 되도록 업그레이드할 탑 집합을 선택한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 55 -10 000 ≤ x, y ≤ 10 000 1 ≤ r ≤ 20 000 -1000 ≤ s ≤ 1000

어떤 두 탑도 좌표가 같지 않다.

작은 데이터 세트

1 ≤ n ≤ 15

큰 데이터 세트

1 ≤ n ≤ 500

첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 탑의 수 n으로 시작한다. 이어지는 n개의 줄에는 각각 4개의 정수 x, y, r, s가 주어진다. 이는 좌표가 x, y이고, 통신 범위가 r이며, 점수(새로운 프로토콜로 업그레이드하는 가치)가 s인 탑을 나타낸다.

각 테스트 케이스마다 다음을 출력한다.

Case #X: score

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, 점수는 탑을 최적으로 선택했을 때의 총점이다.