Куб разлинован на 
клеток (
). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд: вглубь вправо, вглубь влево или вниз. По команде вглубь вправо Робот перемещается в соседнюю правую клетку, по команде вглубь влево он перемещается в соседнюю левую клетку, по команде вниз – в соседнюю нижнюю. То есть, например, для угла 
робот сможет попасть в углы 
, 
, 
для рисунка ниже. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке куба лежит монета достоинством от 
до 
. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Определите максимальную денежную сумму, которую может собрать Робот, пройдя из угла с номером 
клетки в угол с номером 
.
Примечание:
Углы куба нумеруются таким образом
Входные данные:
В первой строчке входных данных содержится единственное число 
. В следующих 
строках содержатся по 
чисел.
Выведите максимальную денежную сумму, которую может собрать робот.
Пример входного файла:
2
Ответ для приведённого примера:
f = open("file.txt")
n = int(f.readline())
a = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
t = list(map(int, f.readline().split()))
a[i][j] = t
for i in a:
print(*i)
dp = [[[0 for k in range(n)] for j in range(n)] for i in range(n)]
dp[0][0][0] = a[0][0][0]
# заполняем грани
for i in range(1, n):
dp[i][0][0] = dp[i - 1][0][0] + a[i][0][0]
for j in range(1, n):
dp[0][j][0] = dp[0][j - 1][0] + a[0][j][0]
for k in range(1, n):
dp[0][0][k] = dp[0][0][k - 1] + a[0][0][k]
# лицевая
for i in range(1, n):
for j in range(1, n):
dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) + a[i][j][0]
# верхняя
for j in range(1, n):
for k in range(1, n):
dp[0][j][k] = max(dp[0][j - 1][k], dp[0][j][k - 1]) + a[0][j][k]
# боковая
for i in range(1, n):
for k in range(1, n):
dp[i][0][k] = max(dp[i - 1][0][k], dp[i][0][k - 1]) + a[i][0][k]
for i in range(1, n):
for j in range(1, n):
for k in range(1, n):
dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]) + a[i][j][k]
print(dp[n - 1][n - 1][n - 1])