本题没有可用的提交语言。

题目描述

给定一个无线网络。每一个无线网络的节点都有一个发射半径r_i，只要两个节点的Euclid距离≤发射节点的半径，另外一个节点就能接收到信息。<o:p></o:p>

现在所有的节点都使用制度A进行信息传输，但现在有一个新的，更好的制度B可用，我们考虑将某些节点更新为使用制度B。<o:p></o:p>

这里有一个限制，如果节点T使用制度B，那么所有可以接收到节点T信息的节点都必须使用制度B，反之则不一定。<o:p></o:p>

你的任务是选择一些节点进行更新。因为更新节点需要一定的费用，并且可以获得一定的收益，我们用score_i来衡量节点i的收益。我们希望所有更新的节点的score之和最大。<o:p></o:p>

输入格式

第一行，数据组数T。每组数据以一个整数N开始，接下来N行每行4个整数：x，y，r，s。他们代表一个节点的坐标（x，y），发射半径r和 score — s。<o:p></o:p>

<o:p></o:p>

输出格式

对于每组数据，输出：<o:p></o:p>

Case  #X:score<o:p></o:p>

其中X表示数据编号，从1开始，score表示该组数据的答案。<o:p></o:p>

Limits<o:p></o:p>

1≤T≤55<o:p></o:p>

-10,000≤x,y≤10,000<o:p></o:p>

1≤r≤20,000<o:p></o:p>

-1000≤s≤1000<o:p></o:p>

Small dataset<o:p></o:p>

1≤n≤15<o:p></o:p>

Large dataset<o:p></o:p>

1≤n≤500<o:p></o:p>

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