eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

В пасьянсе "Корова" используется набор из n * 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 очко, 22 очка, ..., 99, 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 — верхняя).

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

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

Пример

Входные данные #1
4
8S AD 3C AC
8C 4H QD QS
5D 9H KC 7H
TC QC AS 2D
Выходные данные #1
69
Источник 2007 USACO US Open, Бронза