두부장수 장홍준 3

장홍준은 꽤 특이한 두부장수다. 세로 크기가 $N$, 가로 크기가 $M$인 두부판을 $2 \times 1$ 크기의 두부로 잘라서 판다. 그런데 두부판은 칸마다 등급이 다르고, $2 \times 1$ 두부의 가격은 그 두부를 이루는 두 칸의 등급에 따라 크게 달라진다. 가격표는 다음과 같다.

예를 들어 등급이 A인 칸과 C인 칸으로 이루어진 두부의 가격은 7이고, D인 칸과 B인 칸으로 이루어진 두부의 가격은 3이다. 표는 대칭이므로 두 칸의 순서는 가격에 영향을 주지 않는다.

두부판의 각 칸에는 A, B, C, D, F 중 하나의 등급이 매겨져 있다. 두부는 가로로 이웃한 두 칸이나 세로로 이웃한 두 칸을 잘라낸 것이고, 한 칸은 두부 하나에만 들어갈 수 있다. 홍준이는 잘라낸 두부 가격의 합이 최대가 되도록 두부판을 자르려고 한다. $2 \times 1$ 두부를 잘라내고 남은 한 칸짜리 두부는 가격이 0이므로 버린다.

홍준이를 도와 잘라낸 두부 가격의 합이 최대가 되도록 두부판을 자르는 프로그램을 작성하시오.

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

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

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