#include <bits/stdc++.h>
using namespace std;
struct Index {
  int n;
  int a[100010];
  Index() { n = 0; }
  void clear() { n = 0; }
  void add(int x) { a[++n] = x; }
  void doit() {
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - (a + 1);
  }
  int ceiling(int v) {
    int x = lower_bound(a + 1, a + n + 1, v) - a;
    if (x > n || a[x] != v) x--;
    return x;
  }
  int floor(int v) { return lower_bound(a + 1, a + n + 1, v) - a; }
  int find(int v) { return lower_bound(a + 1, a + n + 1, v) - a; }
};
struct point {
  int x, y;
  point() {}
  point(int _x, int _y) {
    x = _x;
    y = _y;
  }
};
point conv(point p) { return point((p.x + p.y) / 2, (p.x - p.y) / 2); }
struct rhombus {
  point ul, dr;
  int empty() { return (ul.x > dr.x || ul.y > dr.y); }
};
rhombus intersect(rhombus a, rhombus b) {
  rhombus c;
  c.ul.x = max(a.ul.x, b.ul.x);
  c.ul.y = max(a.ul.y, b.ul.y);
  c.dr.x = min(a.dr.x, b.dr.x);
  c.dr.y = min(a.dr.y, b.dr.y);
  return c;
}
rhombus gen(point a, int dist) {
  rhombus c;
  c.ul.x = a.x - dist + a.y;
  c.ul.y = a.x - dist - a.y;
  c.dr.x = a.x + dist + a.y;
  c.dr.y = a.x + dist - a.y;
  return c;
}
rhombus expand(rhombus a, int dist) {
  rhombus c;
  c.ul.x = a.ul.x - dist;
  c.ul.y = a.ul.y - dist;
  c.dr.x = a.dr.x + dist;
  c.dr.y = a.dr.y + dist;
  return c;
}
void printp(point p) { printf("%d %d\n", p.x, p.y); }
void print(rhombus r) {
  printp(conv(r.ul));
  printp(conv(r.dr));
  printp(conv(point(r.ul.x, r.dr.y)));
  printp(conv(point(r.dr.x, r.ul.y)));
}
struct Manhattan_Closest_Point {
  struct node {
    int maxv;
    node *lc, *rc;
  };
  node *root;
  void update(node *res) { res->maxv = max(res->lc->maxv, res->rc->maxv); }
  node *build(int bg, int ed) {
    node *res;
    res = new node;
    int mid = (bg + ed) >> 1;
    res->maxv = -1000000000;
    if (bg == ed) {
      res->lc = res->rc = NULL;
      return res;
    }
    res->lc = build(bg, mid);
    res->rc = build(mid + 1, ed);
    return res;
  }
  node *serere(int left, int right, node *cur, int pl, int dt) {
    node *res;
    res = new node;
    *res = *cur;
    if (left == right) {
      res->maxv = dt;
      return res;
    }
    int mid = (left + right) >> 1;
    if (pl <= mid)
      res->lc = serere(left, mid, cur->lc, pl, dt);
    else
      res->rc = serere(mid + 1, right, cur->rc, pl, dt);
    update(res);
    return res;
  }
  int query(int left, int right, node *cur, int bg, int ed) {
    if (bg <= left && right <= ed) return cur->maxv;
    int mid = (left + right) >> 1;
    if (ed <= mid) return query(left, mid, cur->lc, bg, ed);
    if (mid < bg) return query(mid + 1, right, cur->rc, bg, ed);
    return max(query(left, mid, cur->lc, bg, ed),
               query(mid + 1, right, cur->rc, bg, ed));
  }
  Index Xindex, Yindex;
  vector<int> vec[100010];
  node *lu[100010], *ru[100010], *ld[100010], *rd[100010];
  void init(point *p, int m) {
    Xindex.clear();
    for (int i = (1); i <= (m); i++) Xindex.add(p[i].x);
    Xindex.doit();
    Yindex.clear();
    for (int i = (1); i <= (m); i++) Yindex.add(p[i].y);
    Yindex.doit();
    for (int i = (1); i <= (Xindex.n); i++) vec[i].clear();
    for (int i = (1); i <= (m); i++)
      vec[Xindex.find(p[i].x)].push_back(Yindex.find(p[i].y));
    node *ept = build(0, Yindex.n + 1);
    lu[0] = ept;
    for (int i = (1); i <= (Xindex.n); i++) {
      lu[i] = lu[i - 1];
      for (vector<int>::iterator iter = vec[i].begin(); iter != vec[i].end();
           iter++)
        lu[i] = serere(0, Yindex.n + 1, lu[i], *iter,
                       Yindex.a[*iter] + Xindex.a[i]);
    }
    ru[Xindex.n + 1] = ept;
    for (int i = (Xindex.n); i >= (1); i--) {
      ru[i] = ru[i + 1];
      for (vector<int>::iterator iter = vec[i].begin(); iter != vec[i].end();
           iter++)
        ru[i] = serere(0, Yindex.n + 1, ru[i], *iter,
                       Yindex.a[*iter] - Xindex.a[i]);
    }
    ld[0] = ept;
    for (int i = (1); i <= (Xindex.n); i++) {
      ld[i] = ld[i - 1];
      for (vector<int>::iterator iter = vec[i].begin(); iter != vec[i].end();
           iter++)
        ld[i] = serere(0, Yindex.n + 1, ld[i], *iter,
                       Xindex.a[i] - Yindex.a[*iter]);
    }
    rd[Xindex.n + 1] = ept;
    for (int i = (Xindex.n); i >= (1); i--) {
      rd[i] = rd[i + 1];
      for (vector<int>::iterator iter = vec[i].begin(); iter != vec[i].end();
           iter++)
        rd[i] = serere(0, Yindex.n + 1, rd[i], *iter,
                       -Xindex.a[i] - Yindex.a[*iter]);
    }
  }
  int querypoint(point p) {
    int res =
        p.x + p.y -
        query(0, Yindex.n + 1, lu[Xindex.ceiling(p.x)], 0, Yindex.ceiling(p.y));
    res = min(res, p.y - p.x -
                       query(0, Yindex.n + 1, ru[Xindex.floor(p.x)], 0,
                             Yindex.ceiling(p.y)));
    res = min(res, p.x - p.y -
                       query(0, Yindex.n + 1, ld[Xindex.ceiling(p.x)],
                             Yindex.floor(p.y), Yindex.n + 1));
    res = min(res, -p.x - p.y -
                       query(0, Yindex.n + 1, rd[Xindex.floor(p.x)],
                             Yindex.floor(p.y), Yindex.n + 1));
    return res;
  }
};
Manhattan_Closest_Point mt;
struct Point_In_Rhombus {
  struct node {
    int count;
    node *lc, *rc;
  };
  node *root;
  node *build(int bg, int ed) {
    node *res;
    res = new node;
    int mid = (bg + ed) >> 1;
    res->count = 0;
    if (bg == ed) {
      res->lc = res->rc = NULL;
      return res;
    }
    res->lc = build(bg, mid);
    res->rc = build(mid + 1, ed);
    return res;
  }
  node *serere(int left, int right, node *cur, int pl) {
    node *res;
    res = new node;
    *res = *cur;
    res->count++;
    if (left == right) return res;
    int mid = (left + right) >> 1;
    if (pl <= mid)
      res->lc = serere(left, mid, cur->lc, pl);
    else
      res->rc = serere(mid + 1, right, cur->rc, pl);
    return res;
  }
  int query(int left, int right, node *cur, int bg, int ed) {
    if (bg <= left && right <= ed) return cur->count;
    int mid = (left + right) >> 1;
    if (ed <= mid) return query(left, mid, cur->lc, bg, ed);
    if (mid < bg) return query(mid + 1, right, cur->rc, bg, ed);
    return query(left, mid, cur->lc, bg, ed) +
           query(mid + 1, right, cur->rc, bg, ed);
  }
  Index Xindex, Yindex;
  vector<int> vec[100010];
  node *t[100010];
  void init(point *p, int m) {
    Xindex.clear();
    for (int i = (1); i <= (m); i++) Xindex.add(p[i].x + p[i].y);
    Xindex.doit();
    Yindex.clear();
    for (int i = (1); i <= (m); i++) Yindex.add(p[i].x - p[i].y);
    Yindex.doit();
    for (int i = (1); i <= (Xindex.n); i++) vec[i].clear();
    for (int i = (1); i <= (m); i++)
      vec[Xindex.find(p[i].x + p[i].y)].push_back(Yindex.find(p[i].x - p[i].y));
    node *ept = build(0, Yindex.n + 1);
    t[0] = ept;
    for (int i = (1); i <= (Xindex.n); i++) {
      t[i] = t[i - 1];
      for (vector<int>::iterator iter = vec[i].begin(); iter != vec[i].end();
           iter++)
        t[i] = serere(0, Yindex.n + 1, t[i], *iter);
    }
  }
  int ask(point p) {
    return query(0, Yindex.n + 1, t[Xindex.ceiling(p.x)], 0,
                 Yindex.ceiling(p.y));
  }
  int queryrhombus(rhombus r) {
    return ask(r.dr) - ask(point(r.dr.x, r.ul.y - 1)) -
           ask(point(r.ul.x - 1, r.dr.y)) + ask(point(r.ul.x - 1, r.ul.y - 1));
  }
};
Point_In_Rhombus gs;
pair<point, int> a[100010];
int cmp(const pair<point, int> &a, const pair<point, int> &b) {
  return a.second > b.second;
}
int check(int n, int have_subway, int t) {
  if (t >= a[1].second) return 1;
  rhombus cur = gen(point(0, 0), 1000000000);
  for (int i = (1); i <= (n); i++) {
    cur = intersect(cur, gen(a[i].first, t));
    if (cur.empty()) break;
    if (i != n && a[i + 1].second > t) continue;
    if (i != n && have_subway) {
      int spare = t - a[i + 1].second;
      if (gs.queryrhombus(expand(cur, spare))) return 1;
    } else if ((i == n) && (!cur.empty()))
      return 1;
  }
  return 0;
}
point metro[100010], dwarf[100010];
void lemon() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); i++) scanf("%d%d", &dwarf[i].x, &dwarf[i].y);
  for (int i = (1); i <= (m); i++) scanf("%d%d", &metro[i].x, &metro[i].y);
  mt.init(metro, m);
  for (int i = (1); i <= (n); i++)
    if (m)
      a[i] = make_pair(dwarf[i], mt.querypoint(dwarf[i]));
    else
      a[i] = make_pair(dwarf[i], 1000000000);
  sort(a + 1, a + n + 1, cmp);
  gs.init(metro, m);
  int left = 0, right = a[1].second;
  while (left != right) {
    int mid = (left + right) >> 1;
    if (check(n, m, mid))
      right = mid;
    else
      left = mid + 1;
  }
  printf("%d\n", left);
}
int main() {
  ios::sync_with_stdio(true);
  lemon();
  return 0;
}
