Cow Solitaire

Late-summer afternoons on the farm pass slowly, and Betsy the cow fills the time playing cow solitaire. It is a far gentler game than the solitaires people play.

Cow solitaire uses an $N \times N$ grid ($3 \le N \le 7$) of playing cards. A deck has four suits — Clubs, Diamonds, Hearts, and Spades — each with 13 ranks: Ace, 2, 3, $\ldots$, 10, Jack, Queen, King. Every card is written with two characters: its rank (A, 2, 3, $\ldots$, 9, T, J, Q, K) followed by its suit (C, D, H, S). A grid with $N = 4$ might look like this:

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

Betsy begins on the card in the lower-left corner and makes exactly $2N - 2$ moves — each one step right or one step up — until she reaches the upper-right corner. She collects the point value of every card on her path: an Ace is worth 1, the number cards 2 through 9 are worth their face value, T is 10, J is 11, Q is 12, and K is 13. Her goal is the highest possible total.

In the grid above, the path TC → QC → AS → 2D → 7H → QS → AC scores $10 + 12 + 1 + 2 + 7 + 12 + 1 = 45$. Going up the left edge and then along the top, TC → 5D → 8C → 8S → AD → 3C → AC scores $10 + 5 + 8 + 8 + 1 + 3 + 1 = 36$. The best route, TC → QC → 9H → KC → QD → QS → AC, scores $10 + 12 + 9 + 13 + 12 + 12 + 1 = 69$.

Help Betsy find the highest score she can reach.

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: line $i+1$ lists the $N$ cards on row $i$ (row 1 is the top row), separated by single spaces and given in left-to-right order.

• A single line containing the highest score Betsy can achieve.