Description

The telecom company created by JYY monopolizes the entire telecom network of the JSOI Kingdom. JYY has built many communication base stations in the JSOI Kingdom. At present, all base stations use the 2G network system. Now the 3G era has arrived, and JYY is thinking about whether to upgrade some base stations to the 3G network.

The JSOI Kingdom can be seen as an infinite two-dimensional plane. JYY has built a total of $n$ communication base stations. The coordinates of the $i$-th base station are $(x_i,y_i)$. Each base station has a communication range $r_i$. Base station $i$ will send information to all base stations whose distance to it is no more than $r_i$.

Upgrading each base station to the 3G network yields a profit $s_i$. This profit may be positive (for example, there is a big city near the base station, so there are many users and the data fees earned are high), or it may be negative (for example, the market around the base station is poor, and the profit cannot cover the investment of upgrading the base station itself). In addition, since base stations that still use the original 2G network system cannot parse information sent from base stations upgraded to the 3G network system (but upgraded base stations can parse information sent from non-upgraded base stations), JYY must ensure that after all upgrade work is completed, for every base station using the 3G network, all base stations within its communication range are also using the 3G network.

Since there are many base stations, can you help JYY compute the maximum profit he can obtain by upgrading base stations?

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain four integers $x_i,y_i,r_i,s_i$, meaning that the communication range of the base station at $(x_i,y_i)$ is $r_i$, and the profit from upgrading it is $s_i$.

The data guarantees that the coordinates of any two base stations are different.

Output Format

Output one integer in one line, representing the maximum profit that can be obtained.

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

5

Hint

Sample Explanation 1

Upgrading the first three base stations can achieve the maximum profit.

Constraints

$1\leq n\leq 500,1\leq r_i\leq 2\times 10^4,-10^4\leq x_i,y_i,s_i\leq 10^4$, and all base station coordinates are pairwise distinct.

Translated by ChatGPT 5