cho.shTofu Seller Jang Hongjun 2
No attempts yetTime limit1sMemory limit256 MBProblem
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.