Коровий пасьянс

Конец лета на ферме - медленное время, очень медленное. Бетси нечего делать, кроме как раскладывать пасьянс "Корова". По очевидным причинам пасьянс "Корова" не так сложен, как любой другой пасьянс, в который играют люди.

В пасьянсе "Корова" используется набор из $n\ast n$ обычных игральных карт с четырьмя мастями (трефы, бубны, черви, пики) из $13$ карт (туз, $2,3,4,...,10$, Валет, Дама, Король). Карты задаются двумя символами: значением $(A,2,3,4,...,9,T,J,Q,K)$ и мастью $(C,D,H,S)$. Ниже приведен типичный набор для $n=4$:

8S AD 3C AC
8C 4H QD QS
5D 9H KC 7H
TC QC AS 2D

Раскладывать этот пасьянс Бетси начинает с нижнего левого угла ($TC$) и продолжает, используя ровно $2\cdot n-2$ ходов "вправо" или "вверх" в правый верхний угол. Попутно она накапливает очки за каждую карту (туз приносит $1$ очко, $2$ — $2$ очка, ..., $9$ — $9$, $T$ дает $10$ баллов, $J-11,Q-12$ и $K-13$) которую она проходит. Цель Бетси — набрать наибольшее количество очков.

Если бы путь Бетси был $TC-QC-AS-2C-7H-QS-AC$, ее оценка была бы $10+12+1+2+7+12+1=45$. Если бы она пошла по левой стороне, а затем по верхней $(TC-5D-8C-8S-AD-3C-AC)$, то ее оценка будет $10+5+8+8+1+3+1=36$, что не так хорошо как первый маршрут. Наилучший результат для этого поля составляет $69$ очков $(TC-QC-9H-KC-QD-QS-AC=10+12+9+13+12+12+1)$.

Бетси хочет знать лучший результат, которого она может достичь. Одна из коров однажды сказала ей что-то о "работе от конца к началу", но она так и не поняла что та имела в виду.

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

Первая строка содержит одно целое число $n(3\le n\le 7)$. Каждая из следующих $n$ строк содержит $n$ карт (строка $1$ — верхняя).

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

Выведите максимально возможное количество очков, которое может набрать Бетси.

Примеры