Maximum Weight Path in a Grid

You are given an n × n grid (1 \leq n \leq 5) containing distinct integers from 1 to \(n^2\). Your task is to determine the maximum weight path sum in the grid. In a valid path, you can start from any cell and move to any of its four neighboring cells (up, down, left, right) without revisiting any cell. The goal is to collect the maximum sum by traversing a sequence of cells.

Note: Since the grid size is small, an exhaustive depth-first search (DFS) approach can be used to try every possible path. The use of DFS is feasible because \(n\) is at most 5.

Example:
For the grid:
1 2
3 4
A possible maximum path is 1 \(\rightarrow\) 2 \(\rightarrow\) 4 \(\rightarrow\) 3, yielding a sum of 10.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) ((1 \leq n \leq 5)). Following this, there are (n) lines, each containing (n) space-separated integers representing the grid. All integers are distinct and range from 1 to (n^2).

outputFormat

Output a single integer via standard output (stdout) representing the maximum weight path sum obtainable by moving through the grid according to the described rules.## sample

1
1

1