Question
Safe Path in Grid
You are given a grid of size KaTeX can only parse string typed expression consisting of integers. Your task is to determine whether there exists a path from the top-left cell KaTeX can only parse string typed expression to the bottom-right cell KaTeX can only parse string typed expression such that you never step on a negative cell. You can only move either right or down at any step.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of rows and columns in the grid.
The next KaTeX can only parse string typed expression lines each contain KaTeX can only parse string typed expression integers representing the grid — KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain KaTeX can only parse string typed expression integers representing the grid — KaTeX can only parse string typed expression.
Output
Print
YES if such a path exists, otherwise print NO.Example
Input
3 3
1 2 3
4 -1 6
7 8 9
Output
YES
Explanation
One valid path is:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
All cells on this path are non-negative, so the answer is YES.
Input
3 3
1 4 3
4 -1 -1
-1 8 9
Output
NO
Explanation
There are no valid paths from (0, 0) to (2, 2).
3 3
1 2 3
4 -1 6
7 8 9
Output
YES
Explanation
One valid path is:
(0,0) → (0,1) → (0,2) → (1,2) → (2,2)
All cells on this path are non-negative, so the answer is YES.
Input
3 3
1 4 3
4 -1 -1
-1 8 9
Output
NO
Explanation
There are no valid paths from (0, 0) to (2, 2).