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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Arthur Petukhovsky petuhovskiy@yandex.ru
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        final int INF = (int) 1e9;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();

            int[] x = new int[k];
            int[] y = new int[k];

            for (int i = 0; i < k; i++) {
                x[i] = in.nextInt();
                y[i] = in.nextInt();
            }

            int ans = INF;

            int l = 0;
            int r = INF;

            //r = 3;
            //l = 3;

            while (l <= r) {
                int mid = (l + r) / 2;
                int kp1 = solve(n, m, x, y, mid);
                if (kp1 <= mid) {
                    ans = Math.min(ans, mid);
                    r = mid - 1;
                } else {
                    ans = Math.min(ans, kp1);
                    l = mid + 1;
                }
            }

            out.println(ans);
        }

        private int solve(int n, int m, int[] x, int[] y, int mid) {
            int k = x.length;

            TaskE.MaxMin fx = new TaskE.MaxMin(0, n + 1);
            TaskE.MaxMin fy = new TaskE.MaxMin(0, m + 1);

            TaskE.Area[] a = new TaskE.Area[k];
            for (int i = 0; i < k; i++) {
                a[i] = new TaskE.Area(x[i], y[i], mid);
            }
            {
                List<Integer> imp = new ArrayList<>();
                imp.add(1);
                imp.add(n);

                for (TaskE.Area area : a) {
                    if (area.lx > 1) imp.add(area.lx - 1);
                    if (area.rx < n) imp.add(area.rx + 1);
                }

                imp.sort(Integer::compareTo);

                for (int ix : imp) {
                    ArrayList<Pair<Integer, Integer>> sg = new ArrayList<>();
                    for (TaskE.Area area : a) {
                        if (area.lx <= ix && area.rx >= ix) {
                            sg.add(new Pair<>(area.ly, area.ry));
                        }
                    }
                    if (!allOnFire(sg, 1, m)) {
                        fx.update(ix);
                        break;
                    }
                }

                if (fx.isEmpty()) return 0;

                Collections.reverse(imp);

                for (int ix : imp) {
                    ArrayList<Pair<Integer, Integer>> sg = new ArrayList<>();
                    for (TaskE.Area area : a) {
                        if (area.lx <= ix && area.rx >= ix) {
                            sg.add(new Pair<>(area.ly, area.ry));
                        }
                    }
                    if (!allOnFire(sg, 1, m)) {
                        fx.update(ix);
                        break;
                    }
                }
            }

            {
                List<Integer> imp = new ArrayList<>();
                imp.add(1);
                imp.add(m);

                for (TaskE.Area area : a) {
                    if (area.ly > 1) imp.add(area.ly - 1);
                    if (area.ry < m) imp.add(area.ry + 1);
                }

                imp.sort(Integer::compareTo);

                for (int iy : imp) {
                    ArrayList<Pair<Integer, Integer>> sg = new ArrayList<>();
                    for (TaskE.Area area : a) {
                        if (area.ly <= iy && area.ry >= iy) {
                            sg.add(new Pair<>(area.lx, area.rx));
                        }
                    }
                    if (!allOnFire(sg, 1, n)) {
                        fy.update(iy);
                        break;
                    }
                }

                Collections.reverse(imp);

                for (int iy : imp) {
                    ArrayList<Pair<Integer, Integer>> sg = new ArrayList<>();
                    for (TaskE.Area area : a) {
                        if (area.ly <= iy && area.ry >= iy) {
                            sg.add(new Pair<>(area.lx, area.rx));
                        }
                    }
                    if (!allOnFire(sg, 1, n)) {
                        fy.update(iy);
                        break;
                    }
                }
            }

            return (Math.max(fx.max - fx.min, fy.max - fy.min) + 1) / 2;
        }

        private boolean allOnFire(ArrayList<Pair<Integer, Integer>> sg, int l, int r) {
            sg.sort(Pair::compare);

            int tr = l - 1;
            for (Pair<Integer, Integer> pii : sg) {
                if (pii.first > tr + 1) return false;
                if (pii.second > tr) tr = pii.second;
            }

            return tr >= r;
        }

        static class Area {
            int lx;
            int ly;
            int rx;
            int ry;

            public Area(int lx, int ly, int rx, int ry) {
                this.lx = lx;
                this.ly = ly;
                this.rx = rx;
                this.ry = ry;
            }

            public Area(int x, int y, int mid) {
                this.lx = x - mid;
                this.ly = y - mid;
                this.rx = x + mid;
                this.ry = y + mid;
            }

        }

        static class MaxMin {
            int max;
            int min;

            public MaxMin(int max, int min) {
                this.max = max;
                this.min = min;
            }

            void update(int x) {
                if (x < min) min = x;
                if (x > max) max = x;
            }

            boolean isEmpty() {
                return min > max;
            }

        }

    }

    static class FastScanner {
        final static int BUFFER_SIZE = 65536;
        BufferedReader br;
        char[] buf = new char[BUFFER_SIZE];
        int len = 0;
        int it = 0;
        boolean end = false;

        boolean delim(char c) {
            return c == ' ' || c == '\n' || c == '\r';
        }

        void fillBuffer() {
            try {
                len = br.read(buf);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        void ensureBuffer() {
            if (it == len) {
                it = 0;
                fillBuffer();
                if (len == -1) end = true;
            }
        }

        void moveNext() {
            while (!end) {
                ensureBuffer();
                if (!delim(buf[it])) return;
                while (it < len && delim(buf[it])) it++;
            }
        }

        public int nextInt() {
            moveNext();
            if (buf[it] == '-') {
                it++;
                return -nextInt();
            }
            if (buf[it] == '+') {
                it++;
                return nextInt();
            }
            int result = 0;
            while (!end) {
                int l = it;
                while (it < len && !delim(buf[it])) {
                    result = (result * 10) + buf[it] - '0';
                    it++;
                }
                ensureBuffer();
                if (end || delim(buf[it])) break;
            }
            return result;
        }

        public FastScanner(String file) {
            try {
                br = new BufferedReader(new FileReader(file), BUFFER_SIZE);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is), BUFFER_SIZE);
        }

    }

    static class Pair<F, S> {
        public F first;
        public S second;

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }

        public int hashCode() {
            int hashFirst = first != null ? first.hashCode() : 0;
            int hashSecond = second != null ? second.hashCode() : 0;

            return (hashFirst + hashSecond) * hashSecond + hashFirst;
        }

        public boolean equals(Object other) {
            if (other instanceof Pair) {
                Pair otherPair = (Pair) other;
                return
                        ((this.first == otherPair.first ||
                                (this.first != null && otherPair.first != null &&
                                        this.first.equals(otherPair.first))) &&
                                (this.second == otherPair.second ||
                                        (this.second != null && otherPair.second != null &&
                                                this.second.equals(otherPair.second))));
            }

            return false;
        }

        public static <F extends Comparable, S extends Comparable> int compare(Pair<F, S> a, Pair<F, S> b) {
            return a.first.compareTo(b.first) != 0 ? a.first.compareTo(b.first) : a.second.compareTo(b.second);
        }

    }
}

