두부 모판 자르기 timer 1초 memory 128MB

KOI 두부 공장에서 만들어내는 크기가 NxN(N≤11)인 두부 모판이 있다. 

이 모판을 1x1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1x2 혹은 2x1 크기)로 잘라서 판매한다. 

그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 

잘려진 포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 그림 1과 같이 정해진다.

포장단위에 있는 두 단위두부가 [A,A]급이면 100원을 받고, [A,B]급이면 70원을, [A,C]급이면 40원을, [B,B]급이면 50원을, [B,C]급이면 30원을, [C,C]급이면 20원을 받는다. 

포장단위에 있는 두 개의 단위두부 중 하나라도 F급이 있으면 이 포장단위는 한푼도 받을 수 없다. 

NxN 두부 모판의 품질이 주어질 때, 가장 높은 가격을 받도록 두부 모판을 1x2 혹은 2x1 크기의 포장단위들로 자르고자 한다. 

예를 들어 그림 2와 같은 3x3 두부 모판이 주어져 있다고 하자.

이 경우, 그림 3과 같이 자르면 4개의 포장단위가 만들어진다.

이때, 이들 포장단위의 가격은 [A,A]=100, [F,C]=0, [A,C]=40, 그리고 [A,B]=70 이다. 

여기서 오른쪽 위 [C]와 같이 단위두부 하나는 포장단위가 아니므로 판매할 수 없다. 따라서 총 가격은 210원이 된다.

이 가격은 그림 2와 같은 3x3 두부모판에서 받을 수 있는 가장 높은 가격이다.

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