The capital of Berland looks like a rectangle of size n × m of the square blocks of same size.

Fire!

It is known that k + 1 blocks got caught on fire (k + 1 ≤ n·m). Those blocks are centers of ignition. Moreover positions of k of these centers are known and one of these stays unknown. All k + 1 positions are distinct.

The fire goes the following way: during the zero minute of fire only these k + 1 centers of ignition are burning. Every next minute the fire goes to all neighbouring blocks to the one which is burning. You can consider blocks to burn for so long that this time exceeds the time taken in the problem. The neighbouring blocks are those that touch the current block by a side or by a corner.

Berland Fire Deparment wants to estimate the minimal time it takes the fire to lighten up the whole city. Remember that the positions of k blocks (centers of ignition) are known and (k + 1)-th can be positioned in any other block.

Help Berland Fire Department to estimate the minimal time it takes the fire to lighten up the whole city.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 109, 1 ≤ k ≤ 500).

Each of the next k lines contain two integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m) — coordinates of the i-th center of ignition. It is guaranteed that the locations of all centers of ignition are distinct.

Output

Print the minimal time it takes the fire to lighten up the whole city (in minutes).

Examples

Input

7 7 3
1 2
2 1
5 5


Output

3


Input

10 5 1
3 3


Output

2

Note

In the first example the last block can have coordinates (4, 4).

In the second example the last block can have coordinates (8, 3).
#include <bits/stdc++.h>
using namespace std;
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
                                           __c, qu[55];
int __f, qr, _eof;
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) {
  x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                   (iS == iT ? EOF : *iS++))
                : *iS++);
}
inline void pc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
inline void pstr(const char *s) {
  int __len = strlen(s);
  for (__f = 0; __f < __len; ++__f) pc(s[__f]);
}
inline void gstr(char *s) {
  for (__c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++);
       __c < 32 || __c > 126 || __c == ' ';)
    __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                    : *iS++);
  for (; __c > 31 && __c < 127 && __c != ' ';
       ++s, __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++))
    *s = __c;
  *s = 0;
}
template <class I>
inline bool gi(I &x) {
  _eof = 0;
  for (__f = 1,
      __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                        (iS == iT ? EOF : *iS++))
                      : *iS++);
       (__c < '0' || __c > '9') && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++)) {
    if (__c == '-') __f = -1;
    _eof |= __c == EOF;
  }
  for (x = 0; __c <= '9' && __c >= '0' && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++))
    x = x * 10 + (__c & 15), _eof |= __c == EOF;
  x *= __f;
  return !_eof;
}
template <class I>
inline void gp(I x) {
  if (!x) pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) pc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::gc;
using io::gi;
using io::gp;
using io::gstr;
using io::pc;
using io::pstr;
void scan() { return; }
template <class T, typename... Args>
void scan(T &a, Args &&...args) {
  gi(a);
  scan(args...);
  return;
}
template <typename T>
void scann(T a, T b) {
  for (auto it = a; it != b; ++it) scan(*it);
}
template <typename T>
void scerr(T a, T b) {
  for (auto it = a; it != b; ++it) cerr << *it << " ";
  cerr << '\n';
}
void print() {
  pc('\n');
  return;
}
template <class T, typename... Args>
void print(T a, Args... args) {
  gp(a);
  pc(' ');
  print(args...);
  return;
}
void cer() { return; }
template <class T, typename... Args>
void cer(T a, Args... args) {
  cerr << " " << a;
  cer(args...);
  return;
}
const int N = 2e5 + 10;
const int M = 1e6 + 2;
const long long mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e16;
void data() {}
int n, m, k, x[N], y[N], COL = 1;
struct tree {
  tree *l, *r;
  int mn, p;
  tree() {
    mn = 0;
    p = 0;
    l = r = nullptr;
  }
} * tx[10000], *ty[10000];
void make(tree *v) {
  if (v->l == nullptr) v->l = new tree();
  if (v->r == nullptr) v->r = new tree();
}
void push(tree *v) {
  if (v->p) {
    make(v);
    v->l->p += v->p;
    v->r->p += v->p;
    v->mn += v->p;
    v->p = 0;
  }
}
void upd(int l, int r, int val, int tl, int tr, tree *v) {
  push(v);
  if (r < tl || tr < l) return;
  if (l <= tl && tr <= r) {
    v->p += val;
    push(v);
    return;
  }
  int tm = (tl + tr) / 2;
  make(v);
  upd(l, r, val, tl, tm, v->l);
  upd(l, r, val, tm + 1, tr, v->r);
  v->mn = min(v->l->mn, v->r->mn);
}
int getmin(int tl, int tr, tree *v) {
  if (v->mn != 0) return inf;
  if (tl == tr) return tl;
  make(v);
  push(v);
  push(v->l);
  push(v->r);
  int tm = (tl + tr) / 2;
  if (v->l->mn == 0)
    return getmin(tl, tm, v->l);
  else
    return getmin(tm + 1, tr, v->r);
}
int getmax(int tl, int tr, tree *v) {
  if (v->mn != 0) return -inf;
  if (tl == tr) return tl;
  make(v);
  push(v);
  push(v->l);
  push(v->r);
  int tm = (tl + tr) / 2;
  if (v->r->mn == 0)
    return getmax(tm + 1, tr, v->r);
  else
    return getmax(tl, tm, v->l);
}
bool check(int t) {
  map<int, vector<pair<int, int>>> evx, evy;
  int nmnx, nmny, nmxx, nmxy, leftx = inf, lefty = inf;
  for (int i = 1; i <= k; ++i) {
    nmnx = max(x[i] - t, 1);
    nmxx = min(x[i] + t, m);
    nmny = max(y[i] - t, 1);
    nmxy = min(y[i] + t, n);
    evx[nmnx].push_back(make_pair(nmny, nmxy));
    evx[nmxx + 1].push_back(make_pair(-nmny, -nmxy));
    evy[nmny].push_back(make_pair(nmnx, nmxx));
    evy[nmxy + 1].push_back(make_pair(-nmnx, -nmxx));
    leftx = min(nmnx - 1, leftx);
    lefty = min(nmny - 1, lefty);
  }
  evx[1].push_back(make_pair(0, 0));
  evy[1].push_back(make_pair(0, 0));
  evx[n].push_back(make_pair(0, 0));
  evy[m].push_back(make_pair(0, 0));
  int ans_min_y = inf;
  int ans_max_y = -inf;
  for (auto i = evx.begin(); i != evx.end(); i++) {
    if (i->first == m + 1) {
      continue;
    }
    for (auto it : i->second) {
      if (it.first == 0) continue;
      if (it.first > 0)
        upd(it.first, it.second, 1, 1, n, tx[COL]);
      else
        upd(-it.first, -it.second, -1, 1, n, tx[COL]);
    }
    ans_min_y = min(ans_min_y, getmin(1, n, tx[COL]));
    ans_max_y = max(ans_max_y, getmax(1, n, tx[COL]));
  }
  int ans_min_x = inf;
  int ans_max_x = -inf;
  for (auto i = evy.begin(); i != evy.end(); i++) {
    if (i->first == n + 1) {
      continue;
    }
    for (auto it : i->second) {
      if (it.first == 0) continue;
      if (it.first > 0)
        upd(it.first, it.second, 1, 1, m, ty[COL]);
      else
        upd(-it.first, -it.second, -1, 1, m, ty[COL]);
    }
    ans_min_x = min(ans_min_x, getmin(1, m, ty[COL]));
    ans_max_x = max(ans_max_x, getmax(1, m, ty[COL]));
  }
  int ret =
      max((ans_max_x - ans_min_x + 1) / 2, (ans_max_y - ans_min_y + 1) / 2);
  COL++;
  return (ret <= t);
}
int main() {
  data();
  scan(m, n, k);
  for (int i = 0; i < 10000; ++i) {
    tx[i] = new tree();
    ty[i] = new tree();
  }
  for (int i = 1; i <= k; ++i) {
    scan(x[i], y[i]);
  }
  int l = -1;
  for (int r = inf; r >= 1; r /= 2) {
    while (l + r <= inf && !check(l + r)) l += r;
  }
  print(l + 1);
  return 0;
}
