1298: Monster-Hunter
Memory Limit:1024 MB
Time Limit:2.000 S
Judge Style:Text Compare
Creator:
Submit:11
Solved:3
Description
“《怪物猎人:荒野》是一款非常好的游戏的说。”—— $LinXce$
$LinXce$ 最近沉迷于怪物猎人荒野,因为封印的龙骸布真的很酷。但是猎人工会的批准流程很麻烦,为了提升狩猎的速度,$LinXce$ 让阿尔玛一次批准狩猎多只怪物。
拿到了批准后,$LinXce$ 来到荒野。地图上记录了 $n$ 只怪物,第 $i$ 只怪物的坐标为 $(x_i, y_i)$,可能有多只怪物在同一个坐标。
但是怪物太多了,$LinXce$ 只能尽可能多狩猎一些。
作为他的随从艾露猫,你发明了呆猫玩偶,距离玩偶不超过 $r$ 的所有怪兽都会被吸引过来。(此处的距离为曼哈顿距离)
定义两点 $P$ 和 $Q$ 之间的距离为曼哈顿距离D,即: $$ D=|Px-Qx|+|Py-Qy| $$
呆猫玩偶很好用,但是只能使用一次。
现在你需要告诉 $LinXce$,在合适的位置使用呆猫玩偶之后,最多可以吸引来多少怪物?
样例解释: 在框选区域内的所有点距离A,B点的曼哈顿距离都小于2。没有合适的位置使用呆猫玩偶能够吸引所有的怪物。
Input
第 $1$ 行输入两个正整数 $n、r$ ($1 \leq n \leq 2*10^5$、$1 \leq r \leq 2*10^8$)
接下来 $n$ 行,每行输入两个整数 $x$、$y$,表示怪物的位置($-10^8 \leq x、y \leq 10^8$)
Output
输出一个整数 $d$ 表示最多能吸引多少怪物。
Sample Input Copy
3 2
1 0
-1 1
3 3
Sample Output Copy
2