#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "URDL";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
struct Point {
  long long x, y;
  Point() {}
  Point(long long x, long long y) : x(x), y(y) {}
  long double abs() const { return hypot(x, y); }
  long double arg() const { return atan2(y, x); }
  Point operator*(double o) const { return Point(x * o, y * o); }
  Point operator+(const Point &o) const { return Point(x + o.x, y + o.y); }
  Point operator-(const Point &o) const { return Point(x - o.x, y - o.y); }
  Point operator/(double o) const { return Point(x / o, y / o); }
  bool operator<(const Point &o) const {
    return x < o.x || (x == o.x && y < o.y);
  }
  friend bool operator==(const Point &r1, const Point &r2) {
    return r1.x == r2.x && r1.y == r2.y;
  }
  Point scale(double o) const { return *this * (o / abs()); }
  Point rotY() const { return Point(-y, x); }
  Point rotX() const { return Point(y, -x); }
  long long cross(Point b) const { return x * b.y - b.x * y; }
  long long dot(Point b) const { return x * b.x + y * b.y; }
  long double disToSeg(Point &a, Point &b) {
    return fabs(((*this) - a).cross(b - a) / (b - a).abs());
  }
  pair<long long, long long> getVec() {
    if (x == 0) return {0, y > 0 ? 1 : -1};
    if (y == 0) return {x < 0 ? -1 : 1, 0};
    long long gg = gcd1(::abs(x), ::abs(y));
    long long px = x / gg, py = y / gg;
    return {px, py};
  }
  void readin() { scanf("%lld%lld", &x, &y); }
  void ppt() { printf("%lld %lld\n", x, y); }
} p[1000035];
int R;
int cnt;
int T[1000035 * 4], lz[1000035 * 4];
void Up(int rt, int l, int r) { T[rt] = max(T[(rt << 1)], T[(rt << 1 | 1)]); }
void Down(int rt, int l, int r) {
  if (lz[rt] != 0) {
    T[(rt << 1)] += lz[rt];
    lz[(rt << 1)] += lz[rt];
    T[(rt << 1 | 1)] += lz[rt];
    lz[(rt << 1 | 1)] += lz[rt];
    lz[rt] = 0;
  }
}
void upt(int rt, int l, int r, int L, int R, int val) {
  if (R <= l || r <= L) return;
  if (L <= l && r <= R) {
    T[rt] += val;
    lz[rt] += val;
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, val);
  upt((rt << 1 | 1), mid, r, L, R, val);
  Up(rt, l, r);
}
int ans;
void fmain(int tid) {
  scanf("%d%d", &n, &R);
  R *= 2;
  vector<pair<int, int> > vp;
  map<int, int> mp;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    p[i].readin();
    p[i] = {p[i].x + p[i].y, p[i].x - p[i].y};
    vp.push_back({p[i].y, i});
    vp.push_back({p[i].y + R + 1, -i});
    mp[(int)p[i].x];
    mp[(int)p[i].x + R];
  }
  for (auto &p : mp) p.second = ++cnt;
  sort(vp.begin(), vp.end());
  int N = vp.size();
  for (int i = 0, j; i < N; i = j) {
    for (j = i; j < N && vp[i].first == vp[j].first; j++)
      ;
    for (int k = i; k < j; k++) {
      int id = vp[k].second;
      int l = (int)p[abs(id)].x;
      int r = mp[l + R];
      l = mp[l];
      if (id > 0) {
        upt(1, 0, cnt, l - 1, r, 1);
      } else {
        upt(1, 0, cnt, l - 1, r, -1);
      }
    }
    maxtt(ans, T[1]);
  }
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

The Cybermen solved that first test much quicker than the Daleks. Luckily for us, the Daleks were angry (shocking!) and they destroyed some of the Cybermen.

After the fighting stopped, Heidi gave them another task to waste their time on.

There are n points on a plane. Given a radius r, find the maximum number of points that can be covered by an L^1-ball with radius r.

An L^1-ball with radius r and center (x_0, y_0) in a 2D-plane is defined as the set of points (x, y) such that the Manhattan distance between (x_0, y_0) and (x, y) is at most r.

Manhattan distance between (x_0, y_0) and (x, y) is defined as |x - x_0| + |y - y_0|.

Input

The first line contains two integers n, r (1 ≤ n ≤ 300 000, 1 ≤ r ≤ 10^6), the number of points and the radius of the ball, respectively. 

Each of the next n lines contains integers x_i, y_i (-10^6 ≤ x_i, y_i ≤ 10^6), describing the coordinates of the i-th point.

It is guaranteed, that all points are distinct.

Output

Print one integer — the maximum number points that an L^1-ball with radius r can cover.

Examples

Input


5 1
1 1
1 -1
-1 1
-1 -1
2 0


Output


3


Input


5 2
1 1
1 -1
-1 1
-1 -1
2 0


Output


5

Note

In the first example, a ball centered at (1, 0) covers the points (1, 1), (1, -1), (2, 0).

In the second example, a ball centered at (0, 0) covers all the points.

Note that x_0 and y_0 need not be integer.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "URDL";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
struct Point {
  long long x, y;
  Point() {}
  Point(long long x, long long y) : x(x), y(y) {}
  long double abs() const { return hypot(x, y); }
  long double arg() const { return atan2(y, x); }
  Point operator*(double o) const { return Point(x * o, y * o); }
  Point operator+(const Point &o) const { return Point(x + o.x, y + o.y); }
  Point operator-(const Point &o) const { return Point(x - o.x, y - o.y); }
  Point operator/(double o) const { return Point(x / o, y / o); }
  bool operator<(const Point &o) const {
    return x < o.x || (x == o.x && y < o.y);
  }
  friend bool operator==(const Point &r1, const Point &r2) {
    return r1.x == r2.x && r1.y == r2.y;
  }
  Point scale(double o) const { return *this * (o / abs()); }
  Point rotY() const { return Point(-y, x); }
  Point rotX() const { return Point(y, -x); }
  long long cross(Point b) const { return x * b.y - b.x * y; }
  long long dot(Point b) const { return x * b.x + y * b.y; }
  long double disToSeg(Point &a, Point &b) {
    return fabs(((*this) - a).cross(b - a) / (b - a).abs());
  }
  pair<long long, long long> getVec() {
    if (x == 0) return {0, y > 0 ? 1 : -1};
    if (y == 0) return {x < 0 ? -1 : 1, 0};
    long long gg = gcd1(::abs(x), ::abs(y));
    long long px = x / gg, py = y / gg;
    return {px, py};
  }
  void readin() { scanf("%lld%lld", &x, &y); }
  void ppt() { printf("%lld %lld\n", x, y); }
} p[1000035];
int R;
int cnt;
int T[1000035 * 4], lz[1000035 * 4];
void Up(int rt, int l, int r) { T[rt] = max(T[(rt << 1)], T[(rt << 1 | 1)]); }
void Down(int rt, int l, int r) {
  if (lz[rt] != 0) {
    T[(rt << 1)] += lz[rt];
    lz[(rt << 1)] += lz[rt];
    T[(rt << 1 | 1)] += lz[rt];
    lz[(rt << 1 | 1)] += lz[rt];
    lz[rt] = 0;
  }
}
void upt(int rt, int l, int r, int L, int R, int val) {
  if (R <= l || r <= L) return;
  if (L <= l && r <= R) {
    T[rt] += val;
    lz[rt] += val;
    return;
  }
  Down(rt, l, r);
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, val);
  upt((rt << 1 | 1), mid, r, L, R, val);
  Up(rt, l, r);
}
int ans;
void fmain(int tid) {
  scanf("%d%d", &n, &R);
  R *= 2;
  vector<pair<int, int> > vp;
  map<int, int> mp;
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    p[i].readin();
    p[i] = {p[i].x + p[i].y, p[i].x - p[i].y};
    vp.push_back({p[i].y, i});
    vp.push_back({p[i].y + R + 1, -i});
    mp[(int)p[i].x];
    mp[(int)p[i].x + R];
  }
  for (auto &p : mp) p.second = ++cnt;
  sort(vp.begin(), vp.end());
  int N = vp.size();
  for (int i = 0, j; i < N; i = j) {
    for (j = i; j < N && vp[i].first == vp[j].first; j++)
      ;
    for (int k = i; k < j; k++) {
      int id = vp[k].second;
      int l = (int)p[abs(id)].x;
      int r = mp[l + R];
      l = mp[l];
      if (id > 0) {
        upt(1, 0, cnt, l - 1, r, 1);
      } else {
        upt(1, 0, cnt, l - 1, r, -1);
      }
    }
    maxtt(ans, T[1]);
  }
  printf("%d\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```