Path Sum in Matrix

You are given an integer matrix of size \(N \times M\) and an integer \(K\). Your task is to determine whether there exists a path from the top-left cell to the bottom-right cell such that the sum of all visited cells equals \(K\). You may only move either right or down at any step.

Formally, starting at cell \((0,0)\) and moving to cell \((N-1, M-1)\) by only moving right or down, does there exist a path where the sum of the matrix elements in the path is exactly \(K\)?

inputFormat

The first line contains three integers: (N) (number of rows), (M) (number of columns), and (K) (target sum). Each of the next (N) lines contains (M) space-separated integers representing the matrix.

outputFormat

Output a single line: "True" if there exists such a path, or "False" otherwise.## sample

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

True