#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = int;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll NN = 2e5, M = 1000000007, L = 20;

const vector<pii> delta = {{1,0},{-1,0},{0,1},{0,-1}};

void run()
{
    int n,m,k; cin >> n >> m >> k;
    int mx_ans = min(n,m);

    vector<vll> g(n,vll(m));
    for(int r,c; int _ : rep(k)){
        cin >> r >> c,--r,--c;
        g[r][c]=1;
    }


    //ans is the length of the min vertical or horizontal distance of 1 squares
    for(int i : rep(n)){
        int last = -1;
        for(int j : rep(m)){
            if(g[i][j]){
                int d = j-last-1;
                if(d) mx_ans = min(mx_ans,d);
                last=j;
            }
        }
        int d = m-last-1;
        if(d) mx_ans = min(mx_ans,d);
    }
    
    for(int j : rep(m)){
        int last = -1;
        for(int i : rep(n)){
            if(g[i][j]){
                int d = i-last-1;
                if(d) mx_ans = min(mx_ans,d);
                last=i;
            }
        }
        int d = n-last-1;
        if(d) mx_ans = min(mx_ans,d);
    }
    auto p = g;
    for(int i : rep(n)){
        for(int j : rep(1,m)) p[i][j]+=p[i][j-1];
    }
    for(int i : rep(1,n)) for(int j : rep(m))
        p[i][j] += p[i-1][j];

    auto query = [&](int r,int c,int k){
        if(r<k-1 or c<k-1) return 1; //not right
        ll here = p[r][c];
        if(r-k>=0) here-=p[r-k][c];
        if(c-k>=0) here-=p[r][c-k];
        if(r-k>=0 and c-k>=0) here+=p[r-k][c-k];
        return here;
    };
    // for(auto &v : g)
        // ranges::copy(v,oit<ll>()),cout<<endl;
    auto check = [&](int k){
        int need = 0,have=0,cover_need=0,cover_have=0;
        pii start = {-1,-1};
        vector<pii> pos;
        for(int i : rep(n)) for(int j : rep(m)) {
            if(!g[i][j] and query(i,j,k)==0) start = {i,j},need++,pos.emplace_back(i,j);
            if(!g[i][j]) cover_need++;
        }
        if(need==0) return false;

        queue<pii> q; vii done(n,vi(m)); q.push(start);
        while(not q.empty()){
            auto [r,c] {q.front()}; q.pop();
            if(done[r][c]) continue;
            have++,done[r][c]=true;
            for(int nr,nc; auto [dr,dc] : delta){
                nr = dr+r,nc=dc+c;
                if(nr<0 or nr>=n)continue;
                if(nc<0 or nc>=m)continue;
                if(done[nr][nc]) continue;
                if(g[nr][nc]) continue;
                if(query(nr,nc,k)) continue;
                q.emplace(nr,nc);
            }
        }

        //no fucking way WE ALSO SWEEPLINE LETS GOOOOOO
        vector<vll> sweep(n,vll(m));
        for(auto [i,j] : pos){
            sweep[i][j]++;
            if(j-k>=0) sweep[i][j-k]--;
        }
        // for(auto &v : sweep) ranges::copy(v,oit<int>()),cout<<endl;
        vector<vll> sweep2(n,vll(m));
        for(int i : rep(n)){
            int cur = 0;
            for(int j : per(m)){
                cur += sweep[i][j];
                if(cur){
                    sweep2[i][j]++;
                    if(i-k>=0) sweep2[i-k][j]--;   
                }
            }
        }
        
        for(int j : rep(m)) {
            int cur = 0;
            for(int i : per(n)){
                cur += sweep2[i][j];
                if(cur) cover_have++;
            }
        }
        // cout << cover_need << " " << cover_have << endl;

        return need==have and cover_need==cover_have;
    };
    // cout << check(2) << endl;
    auto ans = *ranges::partition_point(rep1(1,mx_ans),[&](int k){ return check(k);});
    ans--;
    if(ans==0) ans=-1;
    cout << ans << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

In file included from /usr/include/c++/13/vector:63,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, int>]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~