F. Maze

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC target("avx,avx2")

constexpr int INF = (int)1e9;
constexpr int N = (int)12e4 + 11;
constexpr int MAXN = (int)3000 + 11;
constexpr int md = (int)1e9+7;

void add(int& a,int b){
    a += b;
    if(a >= md) a -= md;
}

mt19937 rnd(time(nullptr));

//vector<pair<int,int>> field;
//vector<pair<int,int>> people;

struct DSU{
    vector<int> parent;
    vector<bool> ok;
    vector<bool> used;
    vector<vector<int>> notOk;
    vector<int> mx;
    DSU(){}
    int n,m;
    DSU(int nn,int mm){
        n = nn, m = mm;
        parent.resize(n*m);
        ok.resize(n*m,false);
        used.resize(n*m,false);
        notOk.resize(n*m);
        for(int i = 0; i < n*m; i++)
            parent[i] = i;
        for(int i = 0; i < n; i++){
            ok[i*m] = 1;
            ok[i*m+m-1] = 1;
        }
        for(int j = 0; j < m; j++){
            ok[j] = 1;
            ok[(n-1)*m+j] = 1;
        }
    }
    void init(int nn,int mm){
        n = nn, m = mm;
        parent.resize(n*m);
        ok.resize(n*m,false);
        used.resize(n*m,false);
        notOk.resize(n*m);
        mx.resize(n*m);
        for(int i = 0; i < n*m; i++)
            parent[i] = i,mx[i] = 0;
        for(int i = 0; i < n; i++){
            ok[i*m] = 1;
            ok[i*m+m-1] = 1;
        }
        for(int j = 0; j < m; j++){
            ok[j] = 1;
            ok[(n-1)*m+j] = 1;
        }
    }
    void clear(){
        for(int i = 0; i < n*m; i++)
            parent[i] = i, used[i] = false, ok[i] = false, notOk[i].clear(), mx[i] = 0;
        for(int i = 0; i < n; i++){
            ok[i*m] = 1;
            ok[i*m+m-1] = 1;
        }
        for(int j = 0; j < m; j++){
            ok[j] = 1;
            ok[(n-1)*m+j] = 1;
        }
    }
    int get(int x){
        return parent[x] == x ? x : parent[x] = get(parent[x]);
    }
    void union_sets(int a,int b){
        used[a] = used[b] = 1;
        a = get(a), b = get(b);
        notOk[a].clear();
        notOk[b].clear();
        if(a == b)
            return;
        ok[a] = ok[b] = (ok[a] || ok[b]);
        if(rnd() % 2)
            swap(a,b);
        parent[a] = b;
        mx[a] = max(mx[a],mx[b]);
    }
    bool check(int pos){
        if(used[pos] == false)
            return false;
        pos = get(pos);
        return ok[pos];
    }
};

DSU d;
int n,m,k;

//bool check(int t){
//    d.clear();
//    int ptr = 0;
//    for(int i = 0; i < people.size(); i++){
//        cerr << "current = " << people[i].second/m+1 << " " << people[i].second%m+1 << "\n";
//        d.mx[get(people[i].second)] = max(d.mx[get(people[i].second)],people[i].first+t);
//        while(ptr < field.size() && field[ptr].first <= people[i].first+t){
//            int pos = field[ptr].second;
//            int x = pos/m,y=pos%m;
//            d.used[pos] = 1;
//            if(y+1<m && d.used[pos+1] && d.mx[get(pos)] >= field[ptr].first)
//                d.union_sets(pos,pos+1);
//            if(y-1>=0 && d.used[pos-1])
//                d.union_sets(pos,pos-1);
//            if(x+1<n && d.used[pos+m])
//                d.union_sets(pos,pos+m);
//            if(x-1>=0 && d.used[pos-m])
//                d.union_sets(pos,pos-m);
//            cerr << "adding " << pos/m+1 << " " << pos%m+1 << "\n";
//            ptr++;
//        }
//        if(d.check(people[i].second) == false){
//            int p = d.get(people[i].second);
//            d.notOk[p].pb(i);
//            if(t == 1)
//                cout << people[i].second / m+1 << " " << people[i].second%m+1 << "\n";
//        }
//    }
//    for(int i = 0; i < n*m; i++)
//        if(!d.notOk[i].empty())
//            return false;
//    return true;
//}
int a[1111][1111];
int mx[1111][1111];
bool ok[1111][1111];
vector<pair<int,pair<int,int>>> people;

const int DX[] = {1,0,-1,0};
const int DY[] = {0,1,0,-1};

bool F(int d){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            mx[i][j] = 0;
            ok[i][j] = 0;
        }
    }
    queue<pair<int,int>> q;
    for(auto& X : people){
        if(mx[X.second.first][X.second.second] != 0)
            continue;
        q.push(mp(X.second.first,X.second.second));
        mx[X.second.first][X.second.second] = X.first+d;
        while(!q.empty()){
            int x,y;
            x = q.front().first, y = q.front().second;
//            if(d == 2)
//                cerr << x << " " << y << "\n";
            q.pop();
            for(int i = 0; i < 4; i++){
                int xn = x + DX[i], yn = y + DY[i];
                if(xn > 0 && xn <= n && yn > 0 && yn <= m && a[xn][yn] <= mx[x][y] && mx[xn][yn] < mx[x][y]){
                    mx[xn][yn] = mx[x][y];
                    q.push(mp(xn,yn));
                }
            }
        }
    }

    queue<pair<int,int>> qq;
    for(int i = 1; i <= n; i++){
        ok[i][1] = ok[i][m] = 1;
        if(mx[i][1])
            qq.push(mp(i,1));
        if(mx[i][m])
            qq.push(mp(i,m));
    }
    for(int j = 1; j <= m; j++){
        ok[1][j] = ok[n][j] = 1;
        if(mx[1][j])
            qq.push(mp(1,j));
        if(mx[n][j])
            qq.push(mp(n,j));
    }
    while(!qq.empty()){
        int x = qq.front().first, y = qq.front().second;
        qq.pop();
        for(int i = 0; i < 4; i++){
            int xn = x + DX[i], yn = y + DY[i];
            if(xn > 0 && xn <= n && yn > 0 && yn <= m && !ok[xn][yn] && mx[xn][yn] == mx[x][y]){
                ok[xn][yn] = 1;
                qq.push(mp(xn,yn));
            }
        }
    }
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= m; j++){
//            cout << mx[i][j] << " ";
//        }
//        cout << "\n";
//    }
    for(auto& x : people){
        if(!ok[x.second.first][x.second.second]){
//            cerr << x.second.first << " " << x.second.second << "\n";
            return false;
        }
    }
    return true;
}

void solve(){
    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < k; i++){
        int x,y,s;
        cin >> x >> y >> s;
        people.pb(mp(s,mp(x,y)));
    }
    sort(people.rbegin(),people.rend());

//    cerr << F(2);
//    return;

    int l = 0, r = (int)1e9;
    while(r - l > 1){
        int m = (r+l)>>1;
        if(F(m))
            r = m;
        else
            l = m;
    }

    if(F(l))
        r = l;
    cout << r << "\n";

    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//      cin >> tests;
    while(tests--){
        solve();
    }
}
/**
1 2 3 4 5 6

**/