#213576. [GCJ 2009 Finals] Wi-fi Towers

You are given a network of wireless towers. Each tower has a range and can send data to neighboring towers as long as the distance is less than or equal to the sending tower's range.

The towers are using an old communication protocol , but there is a new, better protocol available. We are thinking about upgrading some towers to send data using protocol to achieve better bandwidth.

There is one important restriction: if a tower is using the new protocol , every tower within 's range must also be running protocol , so that they can understand the data sent from . The reverse is not necessary — towers running the new protocol can be sent data from towers using the old protocol .

Your task is to select the best set of towers to upgrade from protocol to protocol . There is some benefit to upgrading a tower, but there are also installation costs. So each tower will have a score, which can be positive or negative, which is the value of upgrading the tower. Choose the set of towers to upgrade in such a way that the total score of the upgraded towers is maximized.

The first line contains the number of test cases, . Each test case starts with the number of towers, . The following lines each contain 4 integers: , , , . They describe a tower at coordinates , having a range of and a score (value of updating to the new protocol) of .

For each test case, output:

Case #: score

where is the test case number, starting from 1, and score is the total score for the best choice of towers.

样例输入 1

1
5
0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20

样例输出 1

Case #1: 5

Limits

• No two towers will have the same coordinates.

Small dataset(3 Pts)

Large dataset(25 Pts)