import java.io.*;
import java.util.*;

/**
 * Use 2D prefix sums, Breadth-First-Search, and Binary Search.
 *
 * 1. Build a 2D prefix sum array to store the number of obstructions in the
 *    rectangle from (0,0) to (i,j) for every i, j. This will be used together
 *    with the inclusion-exclusion principle to determine the number of
 *    obstructions in any rectangle from (r1,c1) to (r2,c2).
 * 2. Binary search on the robot size.
 * 3. For each robot size, determine if all unobstructed cells can be reached:
 *    a. Iterate over all possible starting locations and check if the robot
 *       fits there. If no valid starting location exists, the robot is too big.
 *    b. Perform a breadth first search from the starting location, by shifting
 *       the robot up/down by one row or column and tracking the top-left corners
 *       of all reachable positions.
 *    c. Build a new 2D prefix sum array of the visited top-left corners. This
 *       will be used to determine if some position was reached that would cover
 *       a particular cell.
 *    d. Iterate over all unobstructed grid cells and check that at least one
 *       position was reached that would cover the grid cell.
 *
 * @author Finn Lidbetter
 */

public class CleaningRobot_Finn {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        int nRows = Integer.parseInt(s[0]);
        int nCols = Integer.parseInt(s[1]);
        int x = Integer.parseInt(s[2]);
        boolean[][] grid = new boolean[nRows][nCols];
        for (int i=0; i<x; i++) {
            s = br.readLine().split(" ");
            int r = Integer.parseInt(s[0])-1;
            int c = Integer.parseInt(s[1])-1;
            grid[r][c] = true;
        }

        int[][] rectPrefixes = buildRectPrefixes(grid);

        int lo = 1;
        int hi = nRows;
        if (nCols<nRows)
            hi = nCols;
        int best = -1;
        while (lo<=hi) {
            int mid = lo + (hi-lo)/2;
            if (hasValid(mid, grid, rectPrefixes)) {
                lo = mid + 1;
                best = mid;
            } else {
                hi = mid - 1;
            }
        }
        System.out.println(best);
    }

    static boolean hasValid(int sz, boolean[][] grid, int[][] rectPrefixes) {
        int nRows = grid.length;
        int nCols = grid[0].length;
        boolean[][] vis = new boolean[nRows][nCols];
        int[] dr = new int[]{1,-1,0,0};
        int[] dc = new int[]{0,0,1,-1};
        LinkedList<Integer> rq = new LinkedList<>();
        LinkedList<Integer> cq = new LinkedList<>();
        boolean startedBFS = false;
        for (int sr=0; sr<nRows-sz+1; sr++) {
            for (int sc=0; sc<nCols-sz+1; sc++) {
                if (!obstructed(sr, sc, sr+sz-1, sc+sz-1, rectPrefixes) && !startedBFS) {
                    startedBFS = true;
                    vis[sr][sc] = true;
                    rq.offer(sr);
                    cq.offer(sc);
                    while (rq.size() > 0) {
                        int cr = rq.poll();
                        int cc = cq.poll();
                        for (int i=0; i<4; i++) {
                            int nr = cr+dr[i];
                            int nc = cc+dc[i];
                            if (nr>=0 && nc>=0 && nr<nRows-sz+1 && nc<nCols-sz+1
                                    && !vis[nr][nc]
                                    && !obstructed(nr,nc,nr+sz-1,nc+sz-1, rectPrefixes)) {
                                vis[nr][nc] = true;
                                rq.offer(nr);
                                cq.offer(nc);
                            }
                        }
                    }
                    break;
                }
            }
            if (startedBFS)
                break;
        }

        int[][] visRectPrefixes = buildRectPrefixes(vis);
        for (int r=0; r<nRows; r++) {
            for (int c=0; c<nCols; c++) {
                if (!grid[r][c]) {
                    int r1 = r-sz+1;
                    int c1 = c-sz+1;
                    if (r1<0)
                        r1 = 0;
                    if (c1<0)
                        c1 = 0;
                    if (countInRectangle(r1,c1,r,c,visRectPrefixes) == 0)
                        return false;
                }
            }
        }
        return true;
    }

    static int[][] buildRectPrefixes(boolean[][] arr) {
        int nRows = arr.length;
        int nCols = arr[0].length;
        int[][] rectPrefixes = new int[nRows][nCols];
        for (int r=0; r<nRows; r++) {
            int[] rowPrefixes = new int[nCols];
            rowPrefixes[0] = arr[r][0] ? 1 : 0;
            for (int c=1; c<nCols; c++) {
                rowPrefixes[c] = rowPrefixes[c-1] + (arr[r][c] ? 1 : 0);
            }
            for (int c=0; c<nCols; c++) {
                if (r==0) {
                    rectPrefixes[r][c] = rowPrefixes[c];
                } else {
                    rectPrefixes[r][c] = rectPrefixes[r-1][c] + rowPrefixes[c];
                }
            }
        }
        return rectPrefixes;
    }
    static int countInRectangle(int r1, int c1, int r2, int c2, int[][] rectPrefixes) {
        if (r1==0 && c1==0)
            return rectPrefixes[r2][c2];
        if (r1==0)
            return rectPrefixes[r2][c2] - rectPrefixes[r2][c1-1];
        if (c1==0)
            return rectPrefixes[r2][c2] - rectPrefixes[r1-1][c2];
        return rectPrefixes[r2][c2] - rectPrefixes[r1-1][c2] - rectPrefixes[r2][c1-1] + rectPrefixes[r1-1][c1-1];
    }
    static boolean obstructed(int r1, int c1, int r2, int c2, int[][] rectPrefixes) {
        return countInRectangle(r1, c1, r2, c2, rectPrefixes) > 0;
    }
}