cho.shTime limit
2s
Memory limit
128 MB
Jang Hongjun sells tofu by cutting an N-by-M tofu board into 2 x 1 pieces. Each cell has one grade: A, B, C, D, or F. The price of a 2 x 1 piece is determined by the two grades it contains.
The price table is as follows.
| 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 order of the two grades does not affect the price. You may cut non-overlapping 2 x 1 pieces either horizontally or vertically. Any single cell that is not included in a piece has value 0 and is discarded. Find the maximum possible total price.
The first line contains the board height N and width M. N and M are integers between 1 and 14, inclusive.
Each of the next N lines contains M characters. Each character is one of A, B, C, D, and F, and represents the grade of that cell.
Print the maximum possible sum of prices of the tofu pieces that are cut.