Maximum Path Length in a Grid with Constrained Sum

You are given a grid of size $R \times C$ populated with non-negative integers and a target integer $k$. Your task is to find the maximum length of a path such that the sum of the numbers along the path is less than or equal to $k$. In the grid, a path is defined as a sequence of cells where each consecutive pair of cells is adjacent vertically or horizontally (i.e. up, down, left, or right). Each cell may be visited at most once in a single path. If no valid path exists, output 0.

For example, consider the following grid and $k=15$:

[ \begin{matrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{matrix} ]

One valid path from cell $(0,0)$ to $(0,1)$ is $1 \to 2$, which has a sum of 3. The goal is to determine the maximum number of cells you can include in such a path while keeping the cumulative sum ( \leq k ).

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains two space-separated integers, R and C, indicating the number of rows and columns of the grid.
• The next R lines each contain C space-separated non-negative integers, representing the grid's cells.
• The last line contains a single integer, k, the maximum allowed sum for a chosen path.

outputFormat

Output a single integer to standard output (stdout), representing the maximum length of a valid path with a total sum \( \leq k \). If no valid path exists, output 0.

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

5