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;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct AddMaxSegmentTree {
	typedef int Val;
	typedef int Add;
	vector<Val> nodes;
	vector<Val> add;
	int n;
	void init(int minN) {
		n = 1; while(n < minN) n *= 2;
		nodes.assign(n * 2, Val());
		add.assign(n * 2, Val());
	}
	Val getRange(int i, int j) {
		if(i >= j) return -INF;
		return getRangeRec(1, i, j, 0, n);
	}
	void addToRange(int i, int j, Add a) {
		if(i < j) addToRangeRec(1, i, j, a, 0, n);
	}
	Val getRangeRec(int i, int qL, int qR, int L, int R) {
		Val a = add[i];
		if(qL <= L && R <= qR)
			return nodes[i] + a;
		if(a != 0) {
			add[i * 2] += a;
			add[i * 2 + 1] += a;
			nodes[i] += a;
			add[i] = 0;
		}
		int mid = (L + R) >> 1;
		Val r = -INF;
		if(qL < mid) amax(r, getRangeRec(i * 2 + 0, qL, qR, L, mid));
		if(mid < qR) amax(r, getRangeRec(i * 2 + 1, qL, qR, mid, R));
		nodes[i] = max(nodes[i * 2] + add[i * 2], nodes[i * 2 + 1] + add[i * 2 + 1]);
		return r;
	}
	void addToRangeRec(int i, int qL, int qR, Add a, int L, int R) {
		if(qL <= L && R <= qR) {
			add[i] += a;
			return;
		}
		int mid = (L + R) >> 1;
		if(qL < mid) addToRangeRec(i * 2 + 0, qL, qR, a, L, mid);
		if(mid < qR) addToRangeRec(i * 2 + 1, qL, qR, a, mid, R);
		nodes[i] = max(nodes[i * 2] + add[i * 2], nodes[i * 2 + 1] + add[i * 2 + 1]);
	}
};


struct Event {
	int L, R;
	int sign;
};
int main() {
	int n; int m; int k;
	while(~scanf("%d%d%d", &n, &m, &k)) {
		vpii ab(k);
		rep(i, k) {
			int y; int x;
			scanf("%d%d", &y, &x);
			ab[i] = { y + x, y - x };
		}
		vector<pair<int, int>> border(n + m - 1, make_pair(INF, -INF));
		auto setborder = [&border](int y, int x) {
			int a = y + x, b = y - x;
			amin(border[a].first, b);
			amax(border[a].second, b);
		};
		rep(y, n) {
			setborder(y, 0);
			setborder(y, m - 1);
		}
		rep(x, m) {
			setborder(0, x);
			setborder(n - 1, x);
		}
		int lo = -1, up = n + m - 1;
		while(up - lo > 0) {
			int mid = (lo + up + 1) / 2;
			vector<vector<Event>> events(n + m);
			for(auto p : ab) {
				int top = max(0, p.first - mid);
				int bot = min(n + m - 1, p.first + 1 + mid);
				int L = max(-m, p.second - mid);
				int R = min(+n, p.second + 1 + mid);
				events[top].push_back(Event{ L, R, +1 });
				events[bot].push_back(Event{ L, R, -1 });
			}
			AddMaxSegmentTree segt[2];
			rep(p, 2) segt[p].init(m + n + 1);
			auto convert = [](int &L, int &R, int p) {
				if((L & 1) != p) ++ L;
				if((R & 1) != p) ++ R;
				L = (L - p) / 2;
				R = (R - p) / 2;
			};
			bool ok = true;
			rep(a, n + m - 1) {
				for(auto e : events[a]) {
					rep(p, 2) {
						int L = e.L, R = e.R;
						convert(L, R, p);
						segt[p].addToRange(L + m, R + m, -e.sign);
					}
				}
				int L = border[a].first, R = border[a].second + 1;
				convert(L, R, a % 2);
				if(segt[a % 2].getRange(L + m, R + m) == 0) {
					ok = false;
					break;
				}
			}
			if(ok)
				up = mid - 1;
			else
				lo = mid;
		}
		printf("%d\n", lo + 1);
	}
	return 0;
}