Tower

时间限制:10s      空间限制:128MB

题目描述

给定一个无线网络。每一个无线网络的节点都有一个发射半径ri,只要两个节点的Euclid距离≤发射节点的半径,另外一个节点就能接收到信息。

现在所有的节点都使用制度A进行信息传输,但现在有一个新的,更好的制度B可用,我们考虑将某些节点更新为使用制度B

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

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


输入格式

第一行,数据组数T。每组数据以一个整数N开始,接下来N行每行4个整数:xyrs。他们代表一个节点的坐标(xy),发射半径r score s


输出格式

对于每组数据,输出:

Case  #X:score

其中X表示数据编号,从1开始,score表示该组数据的答案。

Limits

1T55

-10,000x,y10,000

1r20,000

-1000s1000

Small dataset

1n15

Large dataset

1n500


样例输入

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

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose