Bessie's Escape from the Bruisers

Bessie is trying to escape while being pursued by N cattle bruisers. Bessie starts at point \((BX, BY)\) at time \(t=0\) and moves with constant velocity \((BVX, BVY)\). At the same time, each cattle bruiser \(i\) starts at \((X_i, Y_i)\) with velocity \((VX_i, VY_i)\). A cattle bruiser can attack Bessie if its Euclidean distance to her is no more than \(R\) at any time \(t\ge0\).

Your task is to compute the maximum number of cattle bruisers that are within the attack range of Bessie at any moment in time. That is, find the maximum count over all \(t\ge0\) for which the number of cattle bruisers satisfying \[ \sqrt{ (X_i + VX_i\,t - (BX + BVX\,t))^2 + (Y_i + VY_i\,t - (BY + BVY\,t))^2 } \le R \] holds.

For each cattle bruiser, note that its condition to be in range reduces to a quadratic inequality in \(t\). You need to determine, for each bruiser, the time interval (if any) during which it can attack Bessie and then find the maximum overlapping intervals count.

inputFormat

The first line contains six numbers: \(BX\), \(BY\), \(BVX\), \(BVY\), \(R\) and \(N\) where \(-1000 \le BX, BY \le 1000\), \(-100 \le BVX, BVY \le 100\), \(1 \le R \le 2500\) and \(1 \le N \le 50000\).

Then \(N\) lines follow. Each of these lines contains four numbers: \(X_i\), \(Y_i\), \(VX_i\) and \(VY_i\) where \(-1000 \le X_i, Y_i \le 1000\) and \(-1000 \le VX_i, VY_i \le 1000\). Each line describes a cattle bruiser’s initial position and velocity.

outputFormat

Output a single integer: the maximum number of cattle bruisers that are within distance \(R\) from Bessie at any time \(t\ge 0\).

sample

0 0 1 0 10 1
5 0 0 0

1