Finding the Maximum Score Path

You are given an $N \times N$ array $A$ whose entries are integers between $-100$ and $100$. Choose one path that starts at $A[1][1]$ and finishes at $A[N][N]$, subject to two restrictions.

1. Every move goes to a cell adjacent up, down, left or right. Diagonal moves are not allowed.
2. A cell that has already been visited cannot be visited again.

When a path obeying both restrictions reaches $A[N][N]$, the sum of the values of all cells it visited is the score of that path. Write a program that finds the largest score a path can have.

The first line contains the size $N$ of the array. ($3 \le N \le 10$)

Each of the next $N$ lines contains $N$ integers separated by spaces. The $j$-th integer on line $i+1$ is $A[i][j]$, and every value is between $-100$ and $100$.

Print the largest path score on the first line.