4 Blocks

Time limit2sMemory limit512 MB

Summary

Fill the empty cells of a small N x M board with 1x1 and 2x2 blocks to maximize total score, given fixed 1x1 blocks.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Brute force
Solved: No attempts yet

Problem

4 Blocks is a cooperative game that two people play on a board. The board is made of $1 \times 1$ square cells. The game has two kinds of blocks: the '1' block and the '4' block. A '1' block is $1 \times 1$ in size, and a '4' block is $2 \times 2$ in size.

Blocks must be placed along the cell boundaries, and no two blocks may overlap. The final score is the sum of the numbers written on the cells. So a '1' block is worth 1 point, and a '4' block is worth 16 points in total, because a 4 is written on each of its four cells.

Hyobin has already placed some '1' blocks on the board. Now Youngsun wants to place '1' blocks and '4' blocks on the rest of the board to make the score as large as possible.

The left picture shows the board as Hyobin left it, and the right picture shows a placement with the maximum score. That score is $4 \times 16 + 6 \times 1 = 70$ .

Input

The first line contains the height $N$ and the width $M$ of the board. ( $1 \le N \le 10$ , $1 \le M \le 25$ )

Each of the next $N$ lines contains a string of length $M$ describing the board Hyobin left. '.' is an empty cell, and '1' is a cell with a '1' block on it.

Output

Print the maximum score Youngsun can get on the first line.

Examples4

Example 1
Input
```
2 11
.....1..1..
..1.....1..
```
Expected output
```
70
```
Example 2
Input
```
5 5
...1.
.....
.1..1
.....
1....
```
Expected output
```
73
```
Example 3
Input
```
4 5
...1.
.1...
..1.1
1....
```
Expected output
```
20
```

Example 4

Input

5 9
.....1...
.....1...
111111111
.....1...
.....1...

Expected output