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).
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Abood1A {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		int m = sc.nextInt();

		int k = sc.nextInt();

		Integer[] ordX = new Integer[k];
		Integer[] ordY = new Integer[k];

		int[] X = new int[k];
		int[] Y = new int[k];

		for (int i = 0; i < k; i++) {
			ordX[i] = i;
			ordY[i] = i;
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt();
		}
		Arrays.sort(ordX, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if(X[o1] != X[o2])
					return X[o1] - X[o2];
				return o1 - o2;
			}
		});

		Arrays.sort(ordY, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				if(Y[o1] != Y[o2])
					return Y[o1] - Y[o2];
				return o1 - o2;
			}
		});

		int lo = 0;
		int hi = (int) 1e9 + 5;
		int ans = -1;
		while(lo <= hi) {
			int mid = (lo + hi) / 2;
			int[] x1 = new int[k];
			int[] x2 = new int[k];
			int[] y1 = new int[k];
			int[] y2 = new int[k];

			ArrayList<Integer> rowTochB = new ArrayList<>();
			ArrayList<Integer> colTochB = new ArrayList<>();
			ArrayList<Integer> rowTochE = new ArrayList<>();
			ArrayList<Integer> colTochE = new ArrayList<>();

			rowTochB.add(1);
			colTochB.add(1);
			rowTochE.add(n);
			colTochE.add(m);

			for (int i = 0; i < k; i++) { 
				x1[i] = Math.max(1, X[i] - mid);
				if(x1[i] - 1 >= 1)
					rowTochE.add(x1[i] - 1);
				x2[i] = Math.min(n, X[i] + mid);
				if(x2[i] + 1 <= n)
					rowTochB.add(x2[i] + 1);
				y1[i] = Math.max(1, Y[i] - mid);
				if(y1[i] - 1 >= 1)
					colTochE.add(y1[i] - 1);
				y2[i] = Math.min(m, Y[i] + mid);
				if(y2[i] + 1 <= m)
					colTochB.add(y2[i] + 1);
			}
			// xxxxxxxxxxxxxxxx
			int sXE = -1;
			for (int i = 0; i < rowTochB.size(); i++) {
				int r = rowTochB.get(i);
				int fE = 1;
				for (int j = 0; j < k; j++) {
					if(r < x1[ordY[j]] || r > x2[ordY[j]])
						continue;
					if(y1[ordY[j]] > fE)
						break;
					else
						fE = y2[ordY[j]] + 1;
				}

				if(fE <= m) {
					if(sXE == -1)
						sXE = r;
					else
						sXE = Math.min(sXE, r);
				}
			}

			int eXE = -1;
			for (int i = 0; i < rowTochE.size(); i++) {
				int r = rowTochE.get(i);
				int fE = 1;
				for (int j = 0; j < k; j++) {
					if(r < x1[ordY[j]] || r > x2[ordY[j]])
						continue;
					if(y1[ordY[j]] > fE)
						break;
					else
						fE = y2[ordY[j]] + 1;
				}
				if(fE <= m) {
					if(eXE == -1)
						eXE = r;
					else
						eXE = Math.max(eXE, r);
				}
			}


			// yyyyyyyyyyyyyyyyyyyy

			int sYE = -1;
			for (int i = 0; i < colTochB.size(); i++) {
				int c = colTochB.get(i);
				int fE = 1;
				for (int j = 0; j < k; j++) {
					if(c < y1[ordX[j]] || c > y2[ordX[j]])
						continue;
					if(x1[ordX[j]] > fE)
						break;
					else
						fE = x2[ordX[j]] + 1;
				}

				if(fE <= n) {
					if(sYE == -1)
						sYE = c;
					else
						sYE = Math.min(sYE, c);
				}
			}

			int eYE = -1;
			for (int i = 0; i < colTochE.size(); i++) {
				int c = colTochE.get(i);
				int fE = 1;
				for (int j = 0; j < k; j++) {
					if(c < y1[ordX[j]] || c > y2[ordX[j]])
						continue;
					if(x1[ordX[j]] > fE)
						break;
					else
						fE = x2[ordX[j]] + 1;
				}

				if(fE <= n) {
					if(eYE == -1)
						eYE = c;
					else
						eYE = Math.max(eYE, c);
				}
			}
			int need = Math.max((eXE - sXE + 1) / 2, (eYE - sYE + 1) / 2);
			if(need <= mid) {
				hi = mid - 1;
				ans = mid;
			}else
				lo = mid + 1;

		}

		out.println(ans);
		out.flush();
		out.close();
	}




	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String file) throws FileNotFoundException{	br = new BufferedReader(new FileReader(file));}


		public String next() throws IOException {
			while(st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}

	}

}

