Find Path with Exact Sum

You are given an integer matrix of dimensions \(N \times M\) and a target integer \(k\). Your task is to determine if there exists a path from the top-left corner to the bottom-right corner of the matrix such that the sum of the numbers along this path is exactly \(k\). The only allowed moves are to the right or downward at each step. Note that the path includes both the starting cell and the ending cell.

inputFormat

The input is given via standard input. The first line contains three integers \(N\), \(M\), and \(k\), where \(N\) and \(M\) represent the number of rows and columns of the matrix respectively, and \(k\) is the target sum. Each of the next \(N\) lines contains \(M\) space-separated integers representing the matrix.

outputFormat

Output a single line via standard output containing either YES if there exists a path with a sum exactly equal to \(k\), or NO otherwise.

3 3 19
5 9 6
1 2 4
8 3 7

YES