두부 모판 자르기

두부 공장에서 만든 크기 $N \times N$인 두부 모판이 있다. 이 모판을 $1 \times 1$ 단위두부 두 개가 붙은 포장단위, 즉 $1 \times 2$ 또는 $2 \times 1$ 크기로 잘라서 판다.

제조 공정 때문에 단위두부의 품질은 A, B, C, F 등급으로 나뉜다. 포장단위의 가격은 그 안에 든 단위두부 두 개의 등급으로 정해지고, 가격표는 다음과 같다.

포장단위의 두 단위두부가 A와 A이면 100원, A와 B이면 70원, A와 C이면 40원, B와 B이면 50원, B와 C이면 30원, C와 C이면 20원을 받는다. 두 단위두부 중 하나라도 F 등급이면 그 포장단위는 한 푼도 받지 못한다.

모판을 자를 때 단위두부를 짝 없이 남겨도 된다. 남은 단위두부는 포장단위가 아니므로 팔 수 없고, 가격에 보태지 않는다.

예를 들어 그림 1의 $3 \times 3$ 모판을 보자.

그림 1. 두부 모판의 예

그림 2처럼 자르면 포장단위 네 개가 만들어진다.

그림 2. 잘린 두부 모판

네 포장단위의 가격은 A와 A가 100원, F와 C가 0원, A와 C가 40원, A와 B가 70원이므로 합이 210원이다. 오른쪽 위의 C는 혼자 남아서 팔 수 없다. 210원이 이 모판에서 받을 수 있는 가장 높은 가격이다.

모판의 크기와 단위두부의 등급이 주어질 때, 모판을 포장단위로 잘라서 받을 수 있는 총 가격의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 두부 모판의 크기 $N$이 주어진다. ($2 \le N \le 11$)

둘째 줄부터 $N$개 줄에 걸쳐 모판의 등급이 첫 번째 행부터 차례로 주어진다. 각 줄은 길이가 $N$이고 등급 사이에 공백이 없으며, 등급은 A, B, C, F 중 하나이다.

첫째 줄에 모판을 포장단위로 잘라서 받을 수 있는 최대 가격을 출력한다.