#include <iostream>

using namespace std;

int n, m, k;
bool safe[505][505] = { };
int best[505][505], val[505][505];

int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> val[i][j];
            best[i][j] = -2000000000;
        }
    }

    for(int i = 0; i < m; i++)
    {
        int r, c, k;
        cin >> r >> c >> k;
        for(int p = r - k; p < r; p++)
        {
            if(p < 1) continue;
            for(int q = c - (p - (r - k)); q <= c + (p - (r - k)); q++)
            {
                if(q < 1) continue;
                if(q > n) break;
                safe[p][q] = true;
            }
        }
        for(int q = c - k; q <= c + k; q++)
        {
            safe[r][q] = true;
        }
        for(int p = r + 1; p <= r + k; p++)
        {
            if(p > n) break;
            for(int q = c - k + (p - r); q <= c + k - (p - r); q++)
            {
                if(q < 1) continue;
                if(q > n) break;
                safe[p][q] = true;
            }
        }
    }

    best[1][1] = val[1][1];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(!safe[i][j] || best[i][j] == -2000000000) continue;
            best[i + 1][j] = max(best[i + 1][j], best[i][j] + val[i + 1][j]);
            best[i][j + 1] = max(best[i][j + 1], best[i][j] + val[i][j + 1]);
        }
    }

    if(best[n][n] == -2000000000) cout << "NO";
    else cout << "YES\n" << best[n][n];
}