Tofu Seller Jang Hongjun 2

Time limit1sMemory limit256 MB

Summary

Pair orthogonally adjacent cells into dominoes priced by the grade table, leaving cells unused for zero, to maximize the total price.

Level: Medium7 of 10
Topics: Graph, Shortest path
Solved: No attempts yet

Problem

Jang Hongjun sells tofu. He starts from a tofu board with N rows and M columns and cuts it into 2x1 pieces. Every square of the board carries its own grade, and the price of one 2x1 piece is decided by the grades of the two squares it covers. The prices are in the table below.

	A	B	C	D	F
A	10	8	7	5	1
B	8	6	4	3	1
C	7	4	3	2	1
D	5	3	2	2	1
F	1	1	1	1	0

The table is symmetric, so the order of the two squares does not change the price. A piece that covers an A square and a C square is worth 7, and a piece that covers a D square and a B square is worth 3.

Every piece covers two squares that touch horizontally or vertically, and pieces cannot overlap. A square that no piece covers is worth 0, so Hongjun throws it away. Write a program that finds the largest total price Hongjun can get from one board.

Input

The first line contains the height N and the width M of the board. N and M are integers between 1 and 50.

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

Output

Print the largest total price of the pieces cut from the board.

Examples8

Example 1
Input
```
4 4
ACFC
FDAB
BACF
DBAC
```
Expected output
```
37
```
Example 2
Input
```
1 1
A
```
Expected output
```
0
```
Example 3
Input
```
1 2
AA
```
Expected output
```
10
```
Example 4
Input
```
2 1
F
F
```
Expected output
```
0
```
Example 5
Input
```
2 2
AF
FA
```
Expected output
```
2
```
Example 6
Input
```
2 2
AA
FF
```
Expected output
```
10
```
Example 7
Input
```
3 3
ABC
DFA
CBD
```
Expected output
```
20
```
Example 8
Input
```
1 7
ABCDFAB
```
Expected output
```
18
```