Tofu Seller Jang Hongjun 3

Jang Hongjun is a rather unusual tofu seller. He has a tofu board with height $N$ and width $M$, and he cuts it into $2 \times 1$ pieces to sell. Each cell of the board has its own grade, and the price of a $2 \times 1$ piece depends on the grades of the two cells it contains. The price table is:

For example, a piece made of an A cell and a C cell costs 7, and a piece made of a D cell and a B cell costs 3. The table is symmetric, so the order of the two cells does not affect the price.

Every cell of the board has one of the grades A, B, C, D, or F. A piece consists of two horizontally adjacent cells or two vertically adjacent cells, and each cell can belong to at most one piece. Hongjun wants to cut the board so that the total price of the cut pieces is as large as possible. Single cells left over after cutting out the $2 \times 1$ pieces are worth 0, so he throws them away.

Write a program that helps Hongjun find the maximum total price of the pieces he cuts out.

The first line contains the height $N$ and the width $M$ of the tofu board. $N$ and $M$ are integers between 1 and 200, inclusive.

Each of the next $N$ lines contains $M$ characters with no spaces. Each character is the grade of the tofu in that cell and is one of A, B, C, D, and F.

Print the maximum total price of the cut pieces on the first line.