두부장수 장홍준 2

장홍준은 두부장수다. 세로 크기가 N, 가로 크기가 M인 두부판을 2x1 크기의 두부로 잘라서 판다. 두부판은 칸마다 두부의 등급이 다르고, 2x1 두부 한 조각의 값은 그 조각이 덮는 두 칸의 등급으로 정해진다. 값은 다음 표를 따른다.

표는 대칭이라서 두 칸의 순서는 값에 영향을 주지 않는다. 예를 들어 A 칸과 C 칸을 함께 덮는 두부의 값은 7이고, D 칸과 B 칸을 함께 덮는 두부의 값은 3이다.

잘라낸 두부 조각은 가로나 세로로 이웃한 두 칸을 덮고, 서로 겹칠 수 없다. 어느 조각에도 들어가지 않은 한 칸짜리 두부는 값이 0이므로 버린다. 홍준이가 두부판 하나에서 얻을 수 있는 두부 값의 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 두부판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 1 이상 50 이하의 정수다.

다음 N개 줄에는 각각 M개의 문자가 공백 없이 주어진다. 각 문자는 그 칸에 있는 두부의 등급이고 A, B, C, D, F 중 하나다.

첫째 줄에 잘라낸 두부 값의 합의 최댓값을 출력한다.