t2

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> min_dist;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void dfs(const vector<vector<int>> &g, int m, int n, int th, int x, int y)
{
    for (int i = 0; i < 4; ++i) {
        int nx = x + dirs[i][0], ny = y + dirs[i][1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx][ny] >= th) {
            if (min_dist[nx][ny] > min_dist[x][y] + 1) {
                min_dist[nx][ny] = min_dist[x][y] + 1;
                dfs(g, m, n, th, nx, ny);
            }
        }
    }
}

int main(int argc, char **argv)
{
    int th, m, n, p;
    cin >> th >> m >> n >> p;
    vector<vector<int>> g(m, vector<int>(n));
    min_dist = vector<vector<int>>(m, vector<int>(n, 1e9));
    for (int i = 0; i < p; ++i) {
        int x, y, d;
        cin >> x >> y >> d;
        for (int a = x - d + 1; a < x + d; ++a)
            if (a >= 0 && a < m)
                for (int b = y - (d - abs(a - x)) + 1; b < y + d - abs(a - x); ++b)
                    if (b >= 0 && b < n)
                        g[a][b] = max(g[a][b], d - abs(a - x) - abs(b - y));
    }
    min_dist[0][0] = 0;
    dfs(g, m, n, th, 0, 0);
    cout << min_dist[m - 1][n - 1] << endl;
    return 0;
};