Cutting the Tofu Board

A tofu factory produces a board of size $N \times N$. The board is cut into packages made of two adjacent $1 \times 1$ tofu units, so every package is $1 \times 2$ or $2 \times 1$, and the packages are sold.

Because of the production process each unit has a quality grade of A, B, C, or F. The price of a package depends on the grades of its two units, as shown in the price table.

A package with two A units sells for 100 won, A and B for 70 won, A and C for 40 won, B and B for 50 won, B and C for 30 won, and C and C for 20 won. If either unit in a package has grade F, the package earns nothing.

You may leave a unit unpaired when you cut the board. A leftover unit is not a package, so it cannot be sold and adds nothing to the total.

Consider the $3 \times 3$ board in figure 1.

Figure 1. An example board

Cutting it as in figure 2 produces four packages.

Figure 2. The board after cutting

The four packages are worth 100 won for A and A, 0 won for F and C, 40 won for A and C, and 70 won for A and B, so the total is 210 won. The C in the top right corner is left alone and cannot be sold. No cut of this board earns more than 210 won.

Given the size of the board and the grade of every unit, write a program that finds the largest total price obtainable by cutting the board into packages.

The first line contains the board size $N$. ($2 \le N \le 11$)

Each of the next $N$ lines contains one row of grades, starting from the first row. Each line has length $N$ with no spaces between grades, and every grade is one of A, B, C, F.

Print the largest total price obtainable by cutting the board into packages.