Search in Sorted Matrix

You are given an ( m \times n ) matrix where each row and each column is sorted in non-decreasing order. Your task is to determine if a given integer ( X ) exists in the matrix.

The matrix is sorted such that for every cell ( A[i][j] ), if one moves to the right or down, the values are non-decreasing. An efficient solution should run in ( O(m+n) ) time by starting from the top-right corner and moving left or down accordingly.

Note: If the matrix is empty, simply return "NO".

inputFormat

The first line of the input contains two integers ( m ) and ( n ) representing the number of rows and columns of the matrix respectively. If ( m > 0 ), the next ( m ) lines each contain ( n ) space-separated integers, representing the matrix. The last line contains an integer ( X ), the number to search for in the matrix.

outputFormat

Print a single line containing either "YES" if ( X ) exists in the matrix, or "NO" otherwise.## sample

3 3
1 4 7
2 5 9
3 6 10
5

YES