Киберлюди прошли первый тест гораздо быстрее, чем Далеки. К счастью для нас, Далеки очень разозлились, и даже уничтожили немного киберлюдей.
После того, как драка прекратилась, Хайди дала им ещё одну времязатратную задачу.
На плоскости даны \(n\) точек, а также дан радиус \(r\). Найдите наибольшее число точек, которые можно покрыть \(L^1\)-шариком с радиусом \(r\).
\(L^1\)-шариком с радиусом \(r\) и центром \((x_0, y_0)\) называется множество точек \((x, y)\), таких что манхэттенское расстояние между \((x_0, y_0)\) и \((x, y)\) не превосходит \(r\).
Манхэттенское расстояние между \((x_0, y_0)\) и \((x, y)\) определяется как \(|x - x_0| + |y - y_0|\).
Выходные данные
Выведите одно целое число — максимальное количество точек, которое может покрыть \(L^1\)-шарик радиуса \(r\).
Примечание
В первом примере шарик с центром \((1, 0)\) покрывает точки \((1, 1)\), \((1, -1)\), \((2, 0)\).
Во втором примере шарик с центром в \((0, 0)\) покрывает все точки.
Обратите внимание, что \(x_0\) и \(y_0\) не обязаны быть целыми числами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1
1 1
1 -1
-1 1
-1 -1
2 0
|
3
|
|
2
|
5 2
1 1
1 -1
-1 1
-1 -1
2 0
|
5
|