#P10590. Magnetic Attraction

    ID: 12613 Type: Default 1000ms 256MiB

Magnetic Attraction

Magnetic Attraction

In a vast field, there are N magnets scattered around. Each magnet is characterized by a 5-tuple \( (x,y,m,p,r) \), where \( x,y \) represent its coordinates, \( m \) is its mass, \( p \) is its magnetic force, and \( r \) is its attraction radius.

A magnet \( A \) can attract another magnet \( B \) if

\[ \sqrt{(x_B-x_0)^2+(y_B-y_0)^2}\leq r_A \quad \text{and} \quad m_B \leq p_A, \]

where \( (x_0,y_0) \) is the fixed location where the collector stands.

Initially, you have your own magnet \( L \) located at \( (x_0,y_0) \) with parameters \( (m_L,p_L,r_L) \). Holding magnet \( L \) (and staying at \( (x_0,y_0) \)), every magnet that can be attracted by \( L \) will be pulled to \( (x_0,y_0) \). At any moment, you may choose any magnet from those you have collected (including \( L \)) to attract additional magnets.

Your task is to determine the maximum number of magnets that can be collected. The initial magnet \( L \) counts towards the total.

inputFormat

The input begins with a line containing six integers: \( N\; x_0\; y_0\; m_L\; p_L\; r_L \), where \( N \) is the number of magnets scattered in the field and \( (x_0,y_0) \) is the location where magnet \( L \) is placed. The parameters \( m_L, p_L, r_L \) are the mass, magnetic force, and attraction radius of magnet \( L \), respectively.

Each of the next \( N \) lines contains five integers: \( x\; y\; m\; p\; r \), representing the coordinates, mass, magnetic force, and attraction radius of a magnet.

outputFormat

Output a single integer, the maximum number of magnets that can be collected (including the initial magnet \( L \)).

sample

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