#include <bits/stdc++.h>
using namespace std;
const long long linf = 4000000000000000000LL;
const int inf = 1000000007;
const long double pi = 3.1415926535;
long long maximum(long long x, long long y) {
  if (x > y) return x;
  return y;
}
long long minimum(long long x, long long y) {
  if (x < y) return x;
  return y;
}
void pv(vector<int> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<long long> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<long double> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<string> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<pair<int, int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).first << " ";
  cout << '\n';
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).second << " ";
  cout << '\n';
}
void pv(vector<pair<long long, long long>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).first << " ";
  cout << '\n';
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).second << " ";
  cout << '\n';
}
void pv(vector<vector<int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<long long>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<vector<int>>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<vector<long long>>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void ps(set<int> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void ps(set<pair<int, int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << i->first << " " << i->second << '\n';
  cout << '\n';
}
void pv(vector<set<int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    ps(*i);
    cout << '\n';
  }
  cout << '\n';
}
void ps(set<string> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pm(map<int, vector<int>> m) {
  for (map<int, vector<int>>::iterator i = m.begin(); i != m.end(); i++) {
    cout << i->first << " ";
    pv(i->second);
  }
}
void pm(map<int, int> m) {
  for (map<int, int>::iterator i = m.begin(); i != m.end(); i++) {
    cout << i->first << " " << i->second << '\n';
  }
}
void pm(map<char, int> m) {
  for (auto i = m.begin(); i != m.end(); i++) {
    cout << i->first << '\n';
    cout << '\t' << i->second << '\n';
  }
}
void pm(map<pair<int, int>, int> m) {
  for (auto i = m.begin(); i != m.end(); i++) {
    cout << i->first.first << " " << i->first.second << " " << i->second
         << '\n';
  }
}
bool comp(pair<int, int> x, pair<int, int> y) {
  if (x.second == y.second) return x.first < y.first;
  return x.second < y.second;
}
int modInverse(int a, int m) {
  int m0 = m;
  int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    int q = a / m;
    int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
long long power(long long x, long long y) {
  long long k = 1 << 30;
  long long z = 1;
  while (k != 0) {
    z *= z;
    z %= inf;
    if (y >= k) {
      z *= x;
      z %= inf;
      y -= k;
    }
    k >>= 1;
  }
  return z;
}
long double area(pair<int, int> x, pair<int, int> y, pair<int, int> z) {
  return ((long long)x.second * y.first + (long long)y.second * z.first +
          (long long)z.second * x.first - (long long)x.first * y.second -
          (long long)y.first * z.second - (long long)z.first * x.second) /
         2.0;
}
bool clockwise(pair<int, int> x, pair<int, int> y, pair<int, int> z) {
  return area(x, y, z) > 0;
}
struct point {
  long double x, y;
};
long double area(point x, point y, point z) {
  return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y -
          z.x * x.y) /
         2.0;
}
bool clockwise(point x, point y, point z) { return area(x, y, z) > 0; }
int gcd(int a, int b) {
  if (a > b) swap(a, b);
  if (a == 0) return b;
  return gcd(a, b % a);
}
int popcount(int a) {
  int count = 0;
  while (a != 0) {
    count += (a % 2);
    a >>= 1;
  }
  return count;
}
class segment_tree {
  struct item {
    int sum, add;
  };
  item single(int i) { return {i, 0}; }
  item merge(item x, item y) {
    item ans;
    ans.sum = max(x.sum, y.sum);
    ans.add = 0;
    return ans;
  }
  vector<item> tree;
  vector<item> A;
  int height;
  item neutral = {0, 0};
  void push(int i, int tl, int tr) {
    tree[i].sum += tree[i].add;
    if (tl != tr) {
      tree[2 * i + 1].add += tree[i].add;
      tree[2 * i + 2].add += tree[i].add;
    }
    tree[i].add = 0;
  }

 public:
  void build(vector<int>& B) {
    int n = B.size();
    height = log2(n - 1) + 1;
    A.resize(n);
    tree.resize((1 << height + 1) - 1);
    for (int i = (0); i < (n); ++i) A[i] = single(B[i]);
    A.resize(1 << height, neutral);
    build(A, 0, 0, (1 << height) - 1);
  }
  void build(vector<item>& A, int v, int tl, int tr) {
    if (tl == tr)
      tree[v] = A[tl];
    else {
      int mid = (tl + tr) / 2;
      build(A, 2 * v + 1, tl, mid);
      build(A, 2 * v + 2, mid + 1, tr);
      tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }

 public:
  int query(int l, int r) { return query(0, 0, (1 << height) - 1, l, r).sum; }
  item query(int v, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return neutral;
    push(v, tl, tr);
    if (l <= tl && r >= tr) {
      return tree[v];
    }
    int mid = (tl + tr) / 2;
    return merge(query(2 * v + 1, tl, mid, l, r),
                 query(2 * v + 2, mid + 1, tr, l, r));
  }

 public:
  void add(int l, int r, int val) { add(0, 0, (1 << height) - 1, l, r, val); }
  void add(int v, int tl, int tr, int l, int r, int val) {
    push(v, tl, tr);
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
      tree[v].add += val;
      push(v, tl, tr);
    } else {
      int mid = (tl + tr) / 2;
      add(2 * v + 1, tl, mid, l, r, val);
      add(2 * v + 2, mid + 1, tr, l, r, val);
      tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
};
long long a, b, c;
void setIO(string second) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
struct range {
  long long start, l, r, size;
};
bool co(range x, range y) {
  if (x.start == y.start) {
    if (x.l == y.l) {
      if (x.r == y.r) {
        return x.size < y.size;
      }
      return x.r < y.r;
    }
    return x.l < y.l;
  }
  return x.start < y.start;
}
const int MAXN = 2000005;
vector<range> A;
int main() {
  setIO("");
  int n, k;
  cin >> n >> k;
  A.resize(2 * n);
  for (int i = (0); i < (n); ++i) {
    cin >> b >> c;
    b += MAXN / 2;
    c += MAXN / 2;
    a = 1;
    A[2 * i] = {max((long long)0, b + c - k), b - c + MAXN - k,
                b - c + MAXN + k, a};
    A[2 * i + 1] = {b + c + k + 1, b - c + MAXN - k, b - c + MAXN + k, -a};
  }
  sort(A.begin(), A.end(), co);
  segment_tree sum;
  vector<int> t(2 * MAXN);
  sum.build(t);
  int ans = 0;
  for (int i = (0); i < (2 * n); ++i) {
    for (int j = (i); j < (2 * n); ++j) {
      if (A[j].start != A[i].start) {
        i = j - 1;
        break;
      }
      sum.add(A[j].l, A[j].r, A[j].size);
    }
    ans = max(ans, sum.query(0, 2 * MAXN - 1));
  }
  cout << ans << '\n';
}

### Prompt

Your challenge is to write 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;
const long long linf = 4000000000000000000LL;
const int inf = 1000000007;
const long double pi = 3.1415926535;
long long maximum(long long x, long long y) {
  if (x > y) return x;
  return y;
}
long long minimum(long long x, long long y) {
  if (x < y) return x;
  return y;
}
void pv(vector<int> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<long long> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<long double> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<string> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pv(vector<pair<int, int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).first << " ";
  cout << '\n';
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).second << " ";
  cout << '\n';
}
void pv(vector<pair<long long, long long>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).first << " ";
  cout << '\n';
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << (*i).second << " ";
  cout << '\n';
}
void pv(vector<vector<int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<long long>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<vector<int>>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void pv(vector<vector<vector<long long>>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    pv(*i);
    cout << '\n';
  }
  cout << '\n';
}
void ps(set<int> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void ps(set<pair<int, int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++)
    cout << i->first << " " << i->second << '\n';
  cout << '\n';
}
void pv(vector<set<int>> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) {
    cout << i - amount.begin() << '\n';
    ps(*i);
    cout << '\n';
  }
  cout << '\n';
}
void ps(set<string> amount) {
  for (auto i = amount.begin(); i != amount.end(); i++) cout << *i << " ";
  cout << '\n';
}
void pm(map<int, vector<int>> m) {
  for (map<int, vector<int>>::iterator i = m.begin(); i != m.end(); i++) {
    cout << i->first << " ";
    pv(i->second);
  }
}
void pm(map<int, int> m) {
  for (map<int, int>::iterator i = m.begin(); i != m.end(); i++) {
    cout << i->first << " " << i->second << '\n';
  }
}
void pm(map<char, int> m) {
  for (auto i = m.begin(); i != m.end(); i++) {
    cout << i->first << '\n';
    cout << '\t' << i->second << '\n';
  }
}
void pm(map<pair<int, int>, int> m) {
  for (auto i = m.begin(); i != m.end(); i++) {
    cout << i->first.first << " " << i->first.second << " " << i->second
         << '\n';
  }
}
bool comp(pair<int, int> x, pair<int, int> y) {
  if (x.second == y.second) return x.first < y.first;
  return x.second < y.second;
}
int modInverse(int a, int m) {
  int m0 = m;
  int y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    int q = a / m;
    int t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
long long power(long long x, long long y) {
  long long k = 1 << 30;
  long long z = 1;
  while (k != 0) {
    z *= z;
    z %= inf;
    if (y >= k) {
      z *= x;
      z %= inf;
      y -= k;
    }
    k >>= 1;
  }
  return z;
}
long double area(pair<int, int> x, pair<int, int> y, pair<int, int> z) {
  return ((long long)x.second * y.first + (long long)y.second * z.first +
          (long long)z.second * x.first - (long long)x.first * y.second -
          (long long)y.first * z.second - (long long)z.first * x.second) /
         2.0;
}
bool clockwise(pair<int, int> x, pair<int, int> y, pair<int, int> z) {
  return area(x, y, z) > 0;
}
struct point {
  long double x, y;
};
long double area(point x, point y, point z) {
  return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y -
          z.x * x.y) /
         2.0;
}
bool clockwise(point x, point y, point z) { return area(x, y, z) > 0; }
int gcd(int a, int b) {
  if (a > b) swap(a, b);
  if (a == 0) return b;
  return gcd(a, b % a);
}
int popcount(int a) {
  int count = 0;
  while (a != 0) {
    count += (a % 2);
    a >>= 1;
  }
  return count;
}
class segment_tree {
  struct item {
    int sum, add;
  };
  item single(int i) { return {i, 0}; }
  item merge(item x, item y) {
    item ans;
    ans.sum = max(x.sum, y.sum);
    ans.add = 0;
    return ans;
  }
  vector<item> tree;
  vector<item> A;
  int height;
  item neutral = {0, 0};
  void push(int i, int tl, int tr) {
    tree[i].sum += tree[i].add;
    if (tl != tr) {
      tree[2 * i + 1].add += tree[i].add;
      tree[2 * i + 2].add += tree[i].add;
    }
    tree[i].add = 0;
  }

 public:
  void build(vector<int>& B) {
    int n = B.size();
    height = log2(n - 1) + 1;
    A.resize(n);
    tree.resize((1 << height + 1) - 1);
    for (int i = (0); i < (n); ++i) A[i] = single(B[i]);
    A.resize(1 << height, neutral);
    build(A, 0, 0, (1 << height) - 1);
  }
  void build(vector<item>& A, int v, int tl, int tr) {
    if (tl == tr)
      tree[v] = A[tl];
    else {
      int mid = (tl + tr) / 2;
      build(A, 2 * v + 1, tl, mid);
      build(A, 2 * v + 2, mid + 1, tr);
      tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }

 public:
  int query(int l, int r) { return query(0, 0, (1 << height) - 1, l, r).sum; }
  item query(int v, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return neutral;
    push(v, tl, tr);
    if (l <= tl && r >= tr) {
      return tree[v];
    }
    int mid = (tl + tr) / 2;
    return merge(query(2 * v + 1, tl, mid, l, r),
                 query(2 * v + 2, mid + 1, tr, l, r));
  }

 public:
  void add(int l, int r, int val) { add(0, 0, (1 << height) - 1, l, r, val); }
  void add(int v, int tl, int tr, int l, int r, int val) {
    push(v, tl, tr);
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
      tree[v].add += val;
      push(v, tl, tr);
    } else {
      int mid = (tl + tr) / 2;
      add(2 * v + 1, tl, mid, l, r, val);
      add(2 * v + 2, mid + 1, tr, l, r, val);
      tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
    }
  }
};
long long a, b, c;
void setIO(string second) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
struct range {
  long long start, l, r, size;
};
bool co(range x, range y) {
  if (x.start == y.start) {
    if (x.l == y.l) {
      if (x.r == y.r) {
        return x.size < y.size;
      }
      return x.r < y.r;
    }
    return x.l < y.l;
  }
  return x.start < y.start;
}
const int MAXN = 2000005;
vector<range> A;
int main() {
  setIO("");
  int n, k;
  cin >> n >> k;
  A.resize(2 * n);
  for (int i = (0); i < (n); ++i) {
    cin >> b >> c;
    b += MAXN / 2;
    c += MAXN / 2;
    a = 1;
    A[2 * i] = {max((long long)0, b + c - k), b - c + MAXN - k,
                b - c + MAXN + k, a};
    A[2 * i + 1] = {b + c + k + 1, b - c + MAXN - k, b - c + MAXN + k, -a};
  }
  sort(A.begin(), A.end(), co);
  segment_tree sum;
  vector<int> t(2 * MAXN);
  sum.build(t);
  int ans = 0;
  for (int i = (0); i < (2 * n); ++i) {
    for (int j = (i); j < (2 * n); ++j) {
      if (A[j].start != A[i].start) {
        i = j - 1;
        break;
      }
      sum.add(A[j].l, A[j].r, A[j].size);
    }
    ans = max(ans, sum.query(0, 2 * MAXN - 1));
  }
  cout << ans << '\n';
}

```