#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e9;
int n, m, px[N], py[N], sx[N], sy[N], dis[N], r[N];
bool ans[N];
bool valid(int x, int y) { return abs(x + y) & 1 ^ 1; }
struct rect {
  int x1, y1, x2, y2;
  void unite(const rect &A) {
    x1 = max(x1, A.x1);
    x2 = min(x2, A.x2);
    y1 = max(y1, A.y1);
    y2 = min(y2, A.y2);
  }
  bool empty() { return x1 > x2 || y1 > y2; }
  rect extend(int r) const { return (rect){x1 - r, y1 - r, x2 + r, y2 + r}; }
  void red() {
    if (x1 == x2) {
      if (!valid(x1, y1)) ++y1;
      if (!valid(x1, y2)) --y2;
    } else if (y1 == y2) {
      if (!valid(x1, y1)) ++x1;
      if (!valid(x2, y1)) --x2;
    }
  }
} q[N];
void rotate(int &x, int &y) {
  int new_x = x + y, new_y = x - y;
  x = new_x;
  y = new_y;
}
struct lsh {
  int st[N], tp;
  void insert(int x) { st[++tp] = x; }
  void build() {
    sort(st + 1, st + tp + 1);
    tp = unique(st + 1, st + tp + 1) - st - 1;
  }
  int find_ge(int x) { return lower_bound(st + 1, st + tp + 1, x) - st; }
  int find_le(int x) { return upper_bound(st + 1, st + tp + 1, x) - st - 1; }
  void clear() { tp = 0; }
} lsh_x, lsh_y;
int tr[N];
void modify(int p) {
  while (p < N) ++tr[p], p += p & -p;
}
int query(int p) {
  int ret = 0;
  while (p) ret += tr[p], p -= p & -p;
  return ret;
}
bool check(rect *q, int tt) {
  static vector<int> mdf[N], qry[N];
  static int mem[N];
  for (int i = 0; i < N; i++) mdf[i].clear(), qry[i].clear(), mem[i] = 0;
  memset(tr, 0, sizeof(tr));
  for (int i = 1; i <= tt; i++) {
    int x1 = lsh_x.find_ge(q[i].x1), y1 = lsh_y.find_ge(q[i].y1);
    int x2 = lsh_x.find_le(q[i].x2), y2 = lsh_y.find_le(q[i].y2);
    q[i] = (rect){x1, y1, x2, y2};
    if (x1 <= x2 && y1 <= y2)
      qry[x1 - 1].push_back(-i), qry[x2].push_back(i);
    else
      ans[i] = 0;
  }
  for (int i = 1; i <= m; i++) mdf[sx[i]].push_back(i);
  for (int i = 1; i <= lsh_x.tp; i++) {
    for (auto t : mdf[i]) modify(sy[t]);
    for (auto t : qry[i]) {
      if (t < 0)
        t = -t, mem[t] = query(q[t].y2) - query(q[t].y1 - 1);
      else if (mem[t] != query(q[t].y2) - query(q[t].y1 - 1))
        return 1;
    }
  }
  return 0;
}
bool check(int mid) {
  rect u = (rect){-inf, -inf, inf, inf};
  vector<int> all;
  for (int i = 1; i <= n; i++) {
    if (dis[i] <= mid)
      r[i] = mid - dis[i], all.push_back(i);
    else {
      u.unite((rect){px[i] - mid, py[i] - mid, px[i] + mid, py[i] + mid});
      u.red();
    }
    if (u.empty()) return 0;
  }
  sort(all.begin(), all.end(), [&](int a, int b) { return r[a] < r[b]; });
  int tt = 0;
  for (int i = 0; i <= int(all.size()); i++) {
    if (i) {
      int x = all[i - 1];
      u.unite((rect){px[x] - mid, py[x] - mid, px[x] + mid, py[x] + mid});
      u.red();
    }
    if (u.empty()) break;
    if (i == int(all.size())) return 1;
    q[++tt] = u.extend(r[all[i]]);
  }
  return check(q, tt);
}
namespace find_nearest {
void rotate_all() {
  for (int i = 1; i <= n; i++) swap(px[i], py[i]), py[i] = -py[i];
  for (int i = 1; i <= m; i++) swap(sx[i], sy[i]), sy[i] = -sy[i];
}
int tr[N << 2];
void modify(int p, int v) {
  while (p < N) tr[p] = max(tr[p], v), p += p & -p;
}
int query(int p) {
  int ret = -inf;
  while (p) ret = max(ret, tr[p]), p -= p & -p;
  return ret;
}
void _work() {
  static vector<int> mdf[N], qry[N];
  lsh_x.clear();
  lsh_y.clear();
  for (int i = 0; i < N; i++) mdf[i].clear(), qry[i].clear();
  for (int i = 1; i <= m; i++) {
    lsh_x.insert(sx[i]);
    lsh_y.insert(sy[i]);
  }
  lsh_x.build();
  lsh_y.build();
  memset(tr, 0xc0, sizeof(tr));
  for (int i = 1; i <= m; i++) mdf[lsh_x.find_le(sx[i])].push_back(i);
  for (int i = 1; i <= n; i++) qry[lsh_x.find_le(px[i])].push_back(i);
  for (int i = 1; i <= lsh_x.tp; i++) {
    for (auto t : mdf[i]) modify(lsh_y.find_le(sy[t]), sx[t] + sy[t]);
    for (auto t : qry[i])
      dis[t] = min(dis[t], px[t] + py[t] - query(lsh_y.find_le(py[t])));
  }
}
void work() {
  memset(dis, 0x3f, sizeof(dis));
  _work();
  rotate_all();
  _work();
  rotate_all();
  _work();
  rotate_all();
  _work();
  rotate_all();
}
}  // namespace find_nearest
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> px[i] >> py[i];
  for (int i = 1; i <= m; i++) cin >> sx[i] >> sy[i];
  find_nearest::work();
  lsh_x.clear();
  lsh_y.clear();
  for (int i = 1; i <= n; i++) {
    rotate(px[i], py[i]);
  }
  for (int i = 1; i <= m; i++) {
    rotate(sx[i], sy[i]);
    lsh_x.insert(sx[i]);
    lsh_y.insert(sy[i]);
  }
  lsh_x.build();
  lsh_y.build();
  for (int i = 1; i <= m; i++) {
    sx[i] = lsh_x.find_ge(sx[i]);
    sy[i] = lsh_y.find_ge(sy[i]);
  }
  int l = 0, r = 2e8;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l;
  return 0;
}
