Description

你将得到一个由无线信号塔组成的网络。每个信号塔都有一定的覆盖半径，并且只要相邻信号塔之间的距离不超过发送塔的覆盖半径，就可以向其发送数据。

这些信号塔目前使用的是旧的通信协议 $A$，但现在有一种更新、更好的协议 $B$ 可供升级。我们正在考虑将部分信号塔升级为协议 $B$，以获得更好的带宽。

但有一个重要的限制：如果某个信号塔 $T$ 升级为新协议 $B$，那么在 $T$ 覆盖范围内的所有信号塔也必须升级为协议 $B$，以便它们能够理解 $T$ 发送的数据。反过来则不要求——使用新协议 $B$ 的信号塔可以接收来自旧协议 $A$ 的信号。

你的任务是选择一组信号塔进行升级，使得升级后信号塔的总得分最大。每个信号塔升级的价值（即得分）可能为正也可能为负。你需要选择升级哪些信号塔，使得升级塔的总得分最大。

Input Format

第一行为测试用例数 $T$。每组测试数据首先给出一个整数 $n$，表示信号塔的数量。接下来的 $n$ 行，每行包含 $4$ 个整数：$x$、$y$、$r$、$s$，分别表示信号塔的坐标 $(x, y)$，覆盖半径 $r$，以及升级该塔的得分 $s$。

Output Format

对于每组测试数据，输出：

Case #$X$: score

其中 $X$ 是测试编号（从 $1$ 开始），score 是你所能获得的最大总得分。

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

Hint

限制条件

• $1 \leq T \leq 55$
• $-10000 \leq x, y \leq 10000$
• $1 \leq r \leq 20000$
• $-1000 \leq s \leq 1000$
• 不会有两个信号塔的坐标完全相同。

小数据集（3 分）

• $1 \leq n \leq 15$

大数据集（25 分）

• $1 \leq n \leq 500$

翻译由 ChatGPT-4.1 完成。