[Usaco2009 Hol]Cattle Bruisers 杀手游戏

在时刻 $0$，贝茜位于 $(BX,BY)$，速度为 $(BVX,BVY)$。共有 $N$ 个杀手，其中第 $i$ 个杀手在时刻 $0$ 位于 $(X_i,Y_i)$，速度为 $(VX_i,VY_i)$。

贝茜和所有杀手均以各自的速度在平面上做匀速直线运动。因此，在任意实数时刻 $t\ge 0$，每个个体的位置均等于其初始位置加上速度与 $t$ 的乘积。

若在某一时刻 $t\ge 0$，某个杀手与贝茜之间的欧氏距离不超过 $R$，则该杀手可以射杀贝茜。距离恰好为 $R$ 时也视为可以射杀。

请计算在贝茜逃脱的过程中，某一时刻能够同时射杀贝茜的杀手数量的最大值。

输入格式

第一行包含六个整数 $N,R,BX,BY,BVX,BVY$。

接下来 $N$ 行，每行包含四个整数 $X_i,Y_i,VX_i,VY_i$，表示第 $i$ 个杀手的初始位置和速度。

输出格式

输出一个整数，表示在逃脱过程中，某一时刻最多有多少个杀手可以射杀贝茜。

样例输入

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

样例输出

2

数据范围

• $1\le N\le 5\times 10^4$；
• $1\le R\le 2\times 10^3$；
• 所有位置坐标和速度分量均为绝对值不超过 $10^3$ 的整数。

来源与许可

本题为 USACO 2009 Holiday 试题「Cattle Bruisers 杀手游戏」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

2