와이파이 통신탑 업그레이드

무선 통신탑 네트워크가 있다. 각 탑에는 도달 거리가 정해져 있고, 그 거리 이하에 있는 다른 탑으로 데이터를 보낼 수 있다.

지금 모든 탑은 구형 통신 규약 A를 쓴다. 대역폭이 더 좋은 신형 규약 B가 나왔고, 일부 탑을 B로 올리려고 한다.

제약이 하나 있다. 어떤 탑 $T$가 신형 규약 B를 쓰면, $T$의 도달 거리 안에 있는 모든 탑도 B를 써야 한다. 그래야 $T$가 보낸 데이터를 알아들을 수 있다. 반대 방향은 필요 없다. 신형 규약 B를 쓰는 탑은 구형 규약 A를 쓰는 탑에서 데이터를 받아도 된다.

업그레이드에는 이득도 있고 설치 비용도 든다. 그래서 각 탑에는 신형 규약으로 올렸을 때의 가치를 나타내는 점수가 하나씩 붙어 있고, 이 점수는 양수일 수도 음수일 수도 있다. 업그레이드할 탑의 집합을 골라서 그 점수의 합을 최대로 만들어라. 한 탑도 고르지 않아도 되며, 그때 합은 0이다.

첫 줄에 테스트 케이스 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 탑의 개수 $n$이 주어진다. 이어지는 $n$개의 줄에는 정수 네 개 $x$, $y$, $r$, $s$가 공백으로 구분되어 주어진다. 좌표 $(x, y)$에 있는 탑의 도달 거리가 $r$이고, 신형 규약으로 올렸을 때의 점수가 $s$라는 뜻이다.

두 탑 사이의 거리는 유클리드 거리다. 탑 $A$에서 탑 $B$까지의 거리가 $A$의 도달 거리 이하이면 $A$는 $B$로 데이터를 보낸다.

제한

• $1 \le T \le 55$
• $1 \le n \le 500$
• $-10000 \le x, y \le 10000$
• $1 \le r \le 20000$
• $-1000 \le s \le 1000$
• 좌표가 같은 탑은 없다.

각 테스트 케이스마다 한 줄씩 다음 형식으로 출력한다.

Case #X: score

$X$는 1부터 시작하는 테스트 케이스 번호이고, score는 가장 좋게 골랐을 때의 점수 합이다.