Zonal Computing Olympiad 2013, 10 Nov 2012

Little Red Riding Hood is carrying a basket with berries through the forest to her grandmother's house.  The forest is arranged in the form of a square N × N grid of cells.  The top left corner cell, where Little Red Riding Hood starts her journey, is numbered (1,1) and the bottom right corner cell, where her grandmother lives, is numbered (N,N).  In each step, she can move either one position right or one position down.

The forest is full of dangerous wolves and she is looking for a safe path to reach her destination.  Little Red Riding Hood's fairy godmother has placed some special anti-wolf magical charms in some of the cells in the grid.  Each charm has a strength.  If the charm in cell (i,j) has strength k then its zone of influence is all the cells within k steps of (i,j); that is, all cells (i',j') such that |i - i'| + |j - j'| ≤ k.  A cell within the zone of influence of a charm is safe from wolves.  A safe path from (1,1) to (N,N) is one in which every cell along the path is safe.

Little Red Riding Hood is carrying a basket with berries. In each cell, she drops some berries while pushing her way through the thick forest.  However, sometimes she is also able to pick up fresh berries.  Each cell is labelled with an integer that indicates the net change in the number of berries in her basket on passing through the cell; that is, the number of berries she picks up in that cell minus the number of berries she drops.  You can assume that there are enough berries in her basket to start with so that the basket never becomes empty.

Little Red Riding Hood knows the positions and strengths of all the magic charms and is looking for a safe path along which the number of berries she has in the basket when she reaches her grandmother's house is maximized.

As an example consider the following grid:

3  3  2  4  3 
2  1 -1 -2  2  
-1  2  4  3 -3  
-2  2  3  2  1  
3 -1  2 -1  2  

Suppose there are 3 magic charms, at position (1,2) with strength 2, at position (4,5) with strength 2 and one at position (4,2) with strength 1.  The positions within the zone of influence of these three charms are indicated in the three grids below using X's.  

X  X  X  X  .         .  .  .  .  .         .  .  .  .  .
X  X  X  .  .         .  .  .  .  X         .  .  .  .  .
.  X  .  .  .         .  .  .  X  X         .  X  .  .  .
.  .  .  .  .         .  .  X  X  X         X  X  X  .  .
.  .  .  .  .         .  .  .  X  X         .  X  .  .  .

Putting these together, the cells that are under the zone of influence of at least one charm are marked with X below.

X  X  X  X  .
X  X  X  .  X
.  X  .  X  X
X  X  X  X  X
.  X  .  X  X

Here are two examples of safe paths in this grid, marked using Y's.  

Y  Y  X  X  .          Y  X  X  X  .
X  Y  X  .  X          Y  Y  X  .  X
.  Y  .  X  X          .  Y  .  X  X
X  Y  Y  Y  Y          X  Y  Y  Y  X
.  X  .  X  Y          .  X  .  Y  Y

Along the first path, she accumulates 19 berries while on the second path she collects 16 berries.  You can verify that among all safe paths, the maximum number of berries she can collect is 19. 

Your task is to help Little Red Riding Hood find out if there is at least one safe path and, if so, compute the maximum number of berries she can collect among all safe paths (which may be a negative number, in which case it is the minimum number of berries she will lose among all safe paths).

-----Input format-----
Line 1: Two space separated integers N and M, giving the dimension of the grid and the number of magic charms, respectively

Lines 2 to N+1: These N lines desribe the grid.  Line i+1 contains N space separated integers, describing the net change in berries in the N cells along row i of the grid.

Lines N+2 to N+M+1: These M lines describe the magic charms.  Each of these lines has 3 integers: the first two integers describe the position of the charm in the grid and the third integer describes its strength.

-----Output format-----
The first line of output must either consist of the word YES, if there are safe paths, or the word NO, if there are no safe paths. If the output on the first line is YES then the second line should contain a single integer giving the maximum number of berries Little Red Riding Hood can collect among all safe paths.  

-----Sample Input-----
5 3
3 3 2 4 3 
2 1 -1 -2 2  
-1 2 4 3 -3  
-2 2 3 2 1  
3 -1 2 -1 2  
1 2 2
4 5 2
4 2 1

-----Sample Output-----
YES
19

-----Test data-----
In all subtasks, you may assume that 2 ≤ N ≤ 500.  Each value on the grid is guaranteed to have absolute value not more than 1000. 
Let K denote the maximum strength among all the magic charms.
- Subtask 1 (30 marks) : 1 ≤ M ≤ 10, 1 ≤ K ≤ 1,000.
- Subtask 2 (70 marks) : 1 ≤ M ≤ 10,000, 1 ≤ K ≤ 10.

-----Live evaluation data-----
- Subtask 1: Testcases 0,1,2,3,4.
- Subtask 2: Testcases 5,6,7,8.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\r\n# import time\r\nimport collections\r\n\r\n\r\ndef solve(n, m, grid, charms):\r\n    newGrid = [[[val, False] for val in row] for row in grid]\r\n\r\n    for x, y, k in charms:\r\n        newGrid[x][y][1] = True\r\n        queue = collections.deque([(x, y, 0)])\r\n        visited = set()\r\n        visited.add((x, y))\r\n\r\n        while queue:\r\n            currX, currY, cost = queue.popleft()\r\n\r\n            for delX, delY in [(-1, 0), (1, 0), (0, 1), (0, -1)]:\r\n                newX, newY = currX + delX, currY + delY\r\n\r\n                if 0 <= newX < n and 0 <= newY < n and (newX, newY) not in visited and cost < k:\r\n                    newGrid[newX][newY][1] = True\r\n                    visited.add((newX, newY))\r\n\r\n                    if cost + 1 <= k:\r\n                        queue.append((newX, newY, cost + 1))\r\n\r\n    # for row in newGrid:\r\n    #     print(row)\r\n\r\n    NEG_INF = float("-inf")\r\n\r\n    dp = [[NEG_INF if not newGrid[i][j][1]\r\n           else newGrid[i][j][0] for j in range(n)] for i in range(n)]\r\n\r\n    # print("After")\r\n    # for row in dp:\r\n    #     for val in row:\r\n    #         if val == NEG_INF:\r\n    #             print(0, end=" ")\r\n    #         else:\r\n    #             print(1, end=" ")\r\n    #     print()\r\n\r\n    # for row in dp:\r\n    #     print(row)\r\n\r\n    for i in range(n):\r\n        for j in range(n):\r\n            if i == 0 and j == 0:\r\n                continue\r\n            elif i == 0:\r\n                dp[i][j] += dp[i][j-1]\r\n            elif j == 0:\r\n                dp[i][j] += dp[i-1][j]\r\n            else:\r\n                dp[i][j] += max(dp[i-1][j], dp[i][j-1])\r\n\r\n    # print("After")\r\n    # for row in dp:\r\n    #     print(row)\r\n\r\n    return (dp[n-1][n-1] != NEG_INF, dp[n-1][n-1])\r\n\r\n\r\n[n, m] = list(map(int, input().strip().split()))\r\n\r\ngrid = []\r\n\r\nfor i in range(n):\r\n    row = list(map(int, input().strip().split()))\r\n    grid.append(row)\r\n\r\ncharms = []\r\n\r\nfor i in range(m):\r\n    [x, y, k] = list(map(int, input().strip().split()))\r\n\r\n    charms.append((x-1, y-1, k))\r\n\r\n# start_time = time.time()\r\nans = solve(n, m, grid, charms)\r\n\r\nif ans[0]:\r\n    print("YES")\r\n    print(ans[1])\r\nelse:\r\n    print("NO")\r\n\r\n# print("--- %s seconds ---" % (time.time() - start_time))\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14584