JYY's telecommunications company holds a monopoly on the entire JSOI Kingdom's telecommunications network. JYY has built many communication base stations in the JSOI Kingdom. Currently, all base stations use the 2G network system. Now that the 3G era has arrived, JYY is considering whether to upgrade some of the base stations to the 3G network.

The JSOI Kingdom can be viewed as an infinite two-dimensional plane. JYY has built a total of $N$ communication base stations, where the $i$-th base station is located at coordinates $(X_i, Y_i)$. Each base station has a communication range $R_i$. The $i$-th base station sends information to all base stations within a distance of $R_i$ from it.

Upgrading each base station to the 3G network yields a profit $S_i$. This profit can be positive (e.g., if there is a large city near the base station with many users, generating significant traffic revenue) or negative (e.g., if the market around the base station is poor, and the profit cannot cover the investment cost of the upgrade).

Furthermore, because the original 2G network base stations cannot parse information sent from 3G network base stations (though upgraded base stations can parse information sent from non-upgraded base stations), JYY must ensure that after all upgrade work is completed, all base stations within the communication range of any 3G network base station also use the 3G network.

Given the large number of base stations, can you help JYY calculate the maximum profit he can obtain by upgrading the base stations?

Input

The first line contains an integer $N$. The next $N$ lines each contain 4 integers $X_i, Y_i, R_i, S_i$, representing that the base station at $(X_i, Y_i)$ has a communication range $R_i$ and an upgrade profit $S_i$.

The data guarantees that no two base stations have the same coordinates.

Output

Output a single integer representing the maximum profit that can be obtained.

Examples

Input 1

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

Output 1

5

Note 1

We can upgrade the first three base stations to the 3G network to obtain the optimal profit.

Constraints

For 30% of the data, $N \le 15$; For 50% of the data, $N \le 75$; For 100% of the data, $1 \le N \le 500$, $1 \le R_i \le 20000$, $|X_i|, |Y_i|, |S_i| \le 10^4$.