SPOJ in Gyumri

   Игра состоит из квадратной доски размера N*N и фишки. Изначально фишка находится в клетке [N,N] и для выигрыша необходимо этой фишкой дойти до клетки [1,1].

   На каждой клетке доски написано какое-то число, которое добавляется к очкам при прохождении фишкой по этой клетке. Необходимо набрать максимально возможное количество очков. Передвигаться из клетки можно только в верхнюю или левую смежные клетки.

Входные данные.

   В первой строке ввода число N - количество строк и столбцов (3≤N≤1000).

   Далее идет само описание доски, т.е. матрицы A[i][j] (-500≤A[i][j]≤500).

Выходные данные.

   Максимальное количество очков, которое можно набрать.

Пример.