C1852 [Contest #13]燕的子安贝-永命线

内存限制:256 MB 时间限制:6000 ms

题目描述

在平面上给定 $n$ 个点和一个 $d$,要求找到一条直线 $l$,使得到 $l$ 的距离不超过 $d$ 的点的个数最大。输出该最大点数。

输入格式

第一行两个整数 $n,d~(1 \le n \le 2\,000, 0 \le d \le 10\,000)$,表示点数和距离限制。

接下来 $n$ 行,每行两个整数 $x,y~(|x|,|y| \le 10\,000)$,表示一个给定的点。

保证给定的 $n$ 个点两两不同。

输出

仅一行一个整数,表示答案。

样例

样例输入 1

9 1 0 0 1 1 -1 1 -1 -1 1 -1 2 0 0 2 -2 0 0 -2

样例输出 1

7

提示