Bomb

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

There are $N$ bombs needing exploding.

Each bomb has three attributes: exploding radius $r_i$, position $(x_i,y_i)$ and lighting-cost $c_i$ which means you need to pay $c_i$ cost making it explode.

If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.

Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.

Input

First line contains an integer $T$, which indicates the number of test cases.

Every test case begins with an integers $N$, which indicates the numbers of bombs.

In the following $N$ lines, the ith line contains four intergers $x_i$, $y_i$, $r_i$ and $c_i$, indicating the coordinate of ith bomb is $(x_i, y_i)$, exploding radius is $r_i$ and lighting-cost is $c_i$.

Limits
- $1 \leq T \leq 20$
- $1 \leq N \leq 1000$
- $-10^8 \leq x_i, y_i, r_i \leq 10^8$
- $1 \leq c_i \leq 10^4$

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.

Sample Input

1 5 0 0 1 5 1 1 1 6 0 1 1 7 3 0 2 10 5 0 1 4

Sample Output

Case #1: 15

Hint

liuyiding

Source

2016年中国大学生程序设计竞赛(杭州)

提交代码