12961296 SUSTech Online Judge
Problem 1296 --Boom

1296: Boom

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 462  Solved: 140
[Submit][Status][Web Board]

Description

Yuki is a grumpy girl and she always wants to make some noise.

One day, Yuki goes to the amusement ground in her university and sets \(n\) bombs. The \(i\)-th bomb set at the position \((x_i,y_i)\) has exploding radius \(r_i\) and lighting-cost \(t_i\), which means that Yuki needs to spend \(t_i\) seconds to config the bomb and make it exploded by remote control.

A bomb will explode instantly if it is in the exploding area (including the boundaries) of any other exploded bombs.

Yuki wants to know the minimum time needed to make all the bombs exploded, and could you give her the answer?

Input

The first line contains an integer \(n\) \((1\leq n\leq 1\ 000)\) --- the number of bombs.

In the following \(n\) lines, the \(i\)-th line contains four integers: \(x_i\), \(y_i\), \(r_i\) and \(t_i\) \((-10^8\leq x_i,y_i\leq 10^8,0\leq r_i,t_i\leq 10\ 000)\) --- parameters of the bomb.

Output

Print one line with the result --- the minimum time cost.

Sample Input

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

Sample Output

15

HINT

Source

 

[Submit][Status]