Max Sum Grid Path

You are given a grid of integers. Your task is to find the maximum possible sum obtainable by traversing exactly \(K\) distinct cells in the grid. You may start at any cell of the grid and you can move to an adjacent cell in one of the four directions: up, down, left, or right.

The path must consist of exactly \(K\) cells, and you cannot revisit a cell in the same path. If it is impossible to construct such a path, output \(-1\).

Due to the small grid sizes, a brute-force depth-first search (DFS) with backtracking is acceptable for solving this problem. Be cautious when handling grid boundaries and visited cells.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. Each test case begins with a line containing three integers \(R\), \(C\), and \(K\), where \(R\) and \(C\) denote the number of rows and columns in the grid, respectively, and \(K\) is the exact number of cells that must be included in the path.

This is followed by \(R\) lines, each containing \(C\) space-separated integers, which represent the grid.

outputFormat

For each test case, output a single line containing the maximum sum obtainable by traversing exactly \(K\) cells. If no valid path exists, output \(-1\).

## sample

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

30
-1
17

</p>