Group Reservation Capacity Check

You are given a grid with \(n\times n\) cells, where each cell \((i,j)\) has a maximum capacity \(C_{ij}\). There are \(m\) groups that wish to reserve seats in specific cells at specific times. Each group is described by four integers \(t, x, y, p\), where:

• \(t\) is the time of the reservation,
• \((x,y)\) is the 1-indexed position in the grid, and
• \(p\) is the number of people in the group.

For each cell, the groups that reserve that cell must be considered in increasing order of time \(t\). Let \(S\) be the cumulative number of people that have been reserved in that cell up to any given time. The cell can accommodate the reservations if and only if \(S \leq C_{ij}\) at all times. Your task is to determine whether it is possible to accommodate all the groups' reservations across the grid without exceeding any cell's capacity.

Note: The input contains the grid capacities and the group reservations, and you should output YES if all reservations can be accommodated, and NO otherwise.

inputFormat

The input is read from standard input (stdin) in the following format:

n m
C11 C12 ... C1n
C21 C22 ... C2n
...
Cn1 Cn2 ... Cnn
t1 x1 y1 p1
t2 x2 y2 p2
...
tm xm ym pm

Where:

• n is the dimension of the grid.
• m is the number of group reservations.
• Each of the next n lines contains n space-separated integers representing the capacities \(C_{ij}\) of the grid cells.
• Each of the next m lines contains four space-separated integers: t (time), x (row index), y (column index), and p (number of people).

outputFormat

Output a single line to standard output (stdout):

YES

If all group reservations can be scheduled without exceeding the capacity of any cell, or

NO

Otherwise.

## sample

3 3
5 5 5
5 5 5
5 5 5
1 1 1 2
2 1 1 1
3 2 2 3

YES