Problem: Problem

Phantom thief Rappan came to steal the jewels. It was easy to get the jewel, but the jewel was equipped with a sensor and was surrounded by security robots.

The guard robot is designed to move towards the jewel. The sensor didn't seem to be easy to remove, so I decided to put a jewel and escape. I decided to keep the jewels as far away from the guard robot as possible to give me time to escape.

The site has a rectangular shape consisting of n x m squares and there are no obstacles. The k-body security robots are arranged in squares (xi, yi) (0 ≤ xi ≤ n−1, 0 ≤ yi ≤ m−1), respectively, and can move to the upper, lower, left and right squares in a unit time. The security robot moves to the square with the jewel in the shortest path.

Find the maximum travel time it takes for one or more guard robots to reach the jeweled square when you are free to place jewels on the premises.

Constraints

* 1 ≤ n, m ≤ 5 × 104
* 1 ≤ k ≤ min (105, n x m)
* 0 ≤ xi ≤ n−1
* 0 ≤ yi ≤ m−1
* All given coordinates are different

Input


n m k
x1 y1
x2 y2
...
xk yk


All inputs are given as integers.
The first line is given n, m, k separated by blanks.
The coordinates (xi, yi) of the square where the guard robot is located are given in the second and subsequent lines k, separated by blanks.

Output

Output the travel time to the place where it takes the longest time for the security robot to reach in one line.

Examples

Input

20 10 1
0 0


Output

28


Input

20 10 2
0 0
17 5


Output

15


Input

20 10 3
0 0
17 5
6 9


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(__i,v.size())cout<<" "<<v[__i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m,k;
pii rob[125252];
const int INF = 830252521;

const int S_MAX = 1<<17;
// seg tree
struct segtree{
  vi dat,sum;
  segtree(){
    init();
  }
  void init(){
    dat.assign(S_MAX*2-1,0);
    sum.assign(S_MAX*2-1,0);
  }
  void add(int l,int r,int v,int a,int b,int k){
    if(r<=a || b<=l)return;
    if(l<=a && b<=r){
      sum[k] += v;
      dat[k] += v;
    }else{
      int m = (a+b)/2;
      add(l,r,v,a,m,2*k+1);
      add(l,r,v,m,b,2*k+2);
      dat[k] = sum[k] + min(dat[2*k+1],dat[2*k+2]);
    }
  }
  void add(int l,int r,int v){
    add(l,r,v,0,S_MAX,0);
  }
  int segmin(int l,int r,int a,int b,int k){
    if(r<=a || b<=l)return INF;
    if(l<=a && b<=r){
      return dat[k];
    }else{
      int m = (a+b)/2;
      return sum[k] + min(segmin(l,r,a,m,2*k+1),segmin(l,r,m,b,2*k+2));
    }
  }
  int segmin(int l,int r){
    return segmin(l,r,0,S_MAX,0);
  }
};

const int C = S_MAX>>1;
bool check(int w){
  // init
  segtree X,Y;
  X.init();
  Y.init();

  int head = 0, tail = 0;
  REP(i,n+m+1){
    // seek and add
    while(head < k){
      if(rob[head].first-w <= i){
        // add
        int x = rob[head].first;
        int y = rob[head].second;
        if((x-w)%2==0){
          X.add((S_MAX+y-w)/2,  (S_MAX+y+w)/2+1,  1);
          Y.add((S_MAX+y-w+1)/2,(S_MAX+y+w-1)/2+1,1);
        }else{
          Y.add((S_MAX+y-w)/2,  (S_MAX+y+w)/2+1,  1);
          X.add((S_MAX+y-w+1)/2,(S_MAX+y+w-1)/2+1,1);
        }
        head++;
      }else{
        break;
      }
    }
    // check
    int up = i<=(n-1) ? i : 2*(n-1)-i;
    int ud = i<=(m-1) ? -i : i-2*(m-1);

    // debug
    // DEBUG(i);
    // printf("%*s 0\n",2*C,"");
    // REP(j,S_MAX)printf("%2d",X.segmin(j,j+1));putchar('\n');
    // REP(j,S_MAX)printf("%2d",Y.segmin(j,j+1));putchar('\n');
    // DEBUG(ud);
    // DEBUG(up);
    // if(i%2==0){
    //   DEBUG(ud/2);
    //   DEBUG(up/2);
    // }else{
    //   DEBUG((ud-1)/2);
    //   DEBUG((up-1)/2);
    // }
    if(i%2==0){
      if(X.segmin((S_MAX+ud)/2,(S_MAX+up)/2+1)==0){
        return false;
      }
    }else{
      if(Y.segmin((S_MAX+ud-1)/2,(S_MAX+up-1)/2+1)==0){
        return false;
      }
    }
    // seek and remove
    while(tail < k){
      if(rob[tail].first+w <= i){
        // add
        int x = rob[tail].first;
        int y = rob[tail].second;
        if((x-w)%2==0){
          X.add((S_MAX+y-w)/2,  (S_MAX+y+w)/2+1,  -1);
          Y.add((S_MAX+y-w+1)/2,(S_MAX+y+w-1)/2+1,-1);
        }else{
          Y.add((S_MAX+y-w)/2,  (S_MAX+y+w)/2+1,  -1);
          X.add((S_MAX+y-w+1)/2,(S_MAX+y+w-1)/2+1,-1);
        }
        tail++;
      }else{
        break;
      }
    }
  }
  return true;
}

int main(){
  scanf("%d%d%d",&n,&m,&k);
  REP(i,k){
    int x,y;
    scanf("%d%d",&x,&y);
    rob[i] = pii(x+y,x-y);
  }
  sort(rob,rob+k);
  int low = -1, high = n+m+2;
  // DEBUG(check(14));
  while(low+1<high){
    int mid = (low+high)/2;
    if(check(mid)){
      high = mid;
    }else{
      low = mid;
    }
  }
  printf("%d\n",high);
  return 0;
}