#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
const int maxn = 1e3+10, maxk = 1e6+10, inf = INT_MAX;

int t[maxn][maxn];
int bl[maxn][maxn];
pair < int, int > p[] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };
int n, m, k;

struct Kid {

    int x, y;
    int courage;

    Kid(){}
    Kid(istream &in) {

        in >> x >> y >> courage;

    }

    inline friend bool operator > (Kid a, Kid b) {

        if (a.courage != b.courage) return a.courage > b.courage;
        return (a.x-1)*m + a.y < (b.x-1)*m + b.y;

    }

} children[maxk];

bool outside(int x, int y) {

    return !(1 <= x && x <= n && 1 <= y && y <= m);

}

bool dfs(int x, int y, int courage, int time) {

    if (outside(x, y) || (bl[x][y] >= 1 && bl[x][y] < time)) return 1;

    bool res = 0;
    bl[x][y] = time;

    for (auto [dx, dy] : p) {

        x += dx;
        y += dy;
        if (t[x][y] <= courage && bl[x][y] != time) res |= dfs(x, y, courage, time);
        x -= dx;
        y -= dy;

    }

    return res;

}

bool check(int d) {

    for (int i = 1 ; i <= k ; ++i) children[i].courage += d;

    memset(bl, 0, sizeof(bl));
    bool all_reached = 1;
    int time = 1;

    for (int i = 1 ; i <= k && all_reached; ++i) {

        if (bl[children[i].x][children[i].y]) continue;
        if (!dfs(children[i].x, children[i].y, children[i].courage, time)) all_reached = 0;
        ++time;

    }

    for (int i = 1 ; i <= k ; ++i) children[i].courage -= d;

    return all_reached;

}

void solve() {

    sort(children+1, children+1+k, greater < Kid > ());

    int l = -1, r = 10, mid;

    while (l < r - 1) {

        mid = (l+r)/2;
        if (!check(mid)) l = mid;
        else r = mid;

    }

    cout << r << '\n';

}

void read() {

    cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; ++i)
        for (int j = 1 ; j <= m ; ++j)
            cin >> t[i][j];

    for (int i = 1 ; i <= k ; ++i)
        children[i] = Kid(cin);


}

void fast_io() {

    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

}

int main () {

    fast_io();
    read();
    solve();

    return 0;

}

/*

5 10 5
5 5 5 5 6 2 2 2 2 2
5 1 1 1 6 1 1 1 1 2
5 1 6 6 6 4 5 3 5 2
5 1 6 1 6 1 5 1 1 2
5 5 6 5 6 5 5 2 2 2
4 6 1
2 9 2
4 9 1
4 4 2
2 3 4

*/