소 솔리테어

늦여름 농장의 오후는 느리게 흘러가고, 젖소 벳시(Betsy)는 시간을 때우려고 소 솔리테어를 한다. 사람이 하는 솔리테어보다 훨씬 단순한 놀이다.

소 솔리테어는 $N \times N$ ($3 \le N \le 7$) 크기의 카드 격자로 진행한다. 한 벌의 카드는 클로버(Clubs), 다이아몬드(Diamonds), 하트(Hearts), 스페이드(Spades)의 네 무늬로 이루어지며, 각 무늬마다 에이스, 2, 3, $\ldots$, 10, 잭, 퀸, 킹의 13개 끗수가 있다. 카드는 두 글자로 적는데, 끗수(A, 2, 3, $\ldots$, 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

벳시는 왼쪽 아래 구석 카드에서 출발해, 매번 오른쪽으로 한 칸 또는 위쪽으로 한 칸씩 정확히 $2N - 2$번 움직여 오른쪽 위 구석 카드에 도착한다. 지나가는 모든 카드의 점수를 합산하는데, 에이스는 1점, 숫자 카드 2부터 9까지는 그 숫자만큼, T는 10점, J는 11점, Q는 12점, K는 13점이다. 목표는 얻을 수 있는 점수의 합을 가장 크게 만드는 것이다.

위 격자에서 TC → QC → AS → 2D → 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$점이다. 가장 좋은 경로 TC → QC → 9H → KC → QD → QS → AC는 $10 + 12 + 9 + 13 + 12 + 12 + 1 = 69$점이다.

벳시가 얻을 수 있는 가장 높은 점수를 구하라.

• 첫째 줄: 정수 $N$ 하나.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 $i$번째 행(1번째 행이 맨 위 행)의 카드 $N$개가 왼쪽에서 오른쪽 순서로, 공백 하나로 구분되어 주어진다.

• 벳시가 얻을 수 있는 가장 높은 점수를 한 줄에 출력한다.