Maximum Profit Upgrade

In the JSOI Kingdom, there are n telecommunication base stations built by JYY. Each base station is located at \( (x_i, y_i) \) and has a communication range \( r_i \). The base station \( i \) broadcasts messages to every base station \( j \) satisfying \( \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \le r_i \). Upgrading a base station to the 3G network brings a profit \( s_i \) (which can be negative if the upgrade cost outweighs the benefits). However, due to incompatibility issues between the 3G and 2G systems, the following constraint must be met after upgrading: for every upgraded base station \( i \), every base station \( j \) that is within its communication range (i.e. \( \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \le r_i \)) must also be upgraded to 3G.

Your task is to choose a subset of base stations to upgrade so that the above condition is satisfied and the total profit is maximized.

Input Constraint Explanation:
There are \( n \) base stations. Each base station has four parameters \( x_i, y_i, r_i, s_i \). The upgrade selection subset \( S \) must satisfy that for every \( i \in S \) and every \( j \) with \( \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \le r_i \), we have \( j \in S \) as well. It is allowed to choose an empty set if upgrading leads to a negative profit.

Hint: This problem can be modeled as a maximum closure problem in a directed graph. Construct a directed graph where there is an edge from node \( i \) to node \( j \) if \( \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \le r_i \). Then assign each node a weight \( s_i \). The goal is to select a closed subset in the graph (i.e. if \( i \) is selected then all its out-neighbors must be selected as well) with maximum total weight. This problem is equivalent to finding a minimum cut in a flow network.

inputFormat

The first line contains an integer \( n \) denoting the number of base stations.

Each of the following \( n \) lines contains four numbers \( x_i \), \( y_i \), \( r_i \) and \( s_i \) representing the coordinates, communication range, and the upgrade profit of the \( i^{th} \) base station respectively.

outputFormat

Output a single integer, the maximum total profit that can be obtained by upgrading a subset of the base stations while satisfying the constraint.

sample

3
0 0 1 5
1 0 1 -3
2 0 1 4

6