Конец лета на ферме - медленное время, очень медленное. Бетси нечего делать, кроме как раскладывать пасьянс "Корова". По очевидным причинам пасьянс "Корова" не так сложен, как любой другой пасьянс, в который играют люди.
В пасьянсе "Корова" используется набор из n∗n обычных игральных карт с четырьмя мастями (трефы, бубны, черви, пики) из 13 карт (туз, 2,3,4,...,10, Валет, Дама, Король). Карты задаются двумя символами: значением (A,2,3,4,...,9,T,J,Q,K) и мастью (C,D,H,S). Ниже приведен типичный набор для n=4:
Раскладывать этот пасьянс Бетси начинает с нижнего левого угла (TC) и продолжает, используя ровно 2⋅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≤n≤7). Каждая из следующих n строк содержит n карт (строка 1 — верхняя).
Выведите максимально возможное количество очков, которое может набрать Бетси.