시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 103 19 16 23.529%

문제

4블럭은 두 사람이 보드에서 진행하는 협동 게임이다. 보드는 1×1 크기의 정사각형 칸으로 이루어져 있다. 이 게임에서 블럭은 두 종류가 있다. 하나는 '1' 블럭이고, 또 다른 하나는 '4' 블럭이다. '1' 블럭의 크기는 1×1이고, '4' 블럭의 크기는 2×2이다.

블럭은 칸의 경계에 맞춰서 놓아야 하며, 두 블럭이 겹치면 안된다. 최종 점수는 각 칸에 써있는 수의 하이다. 따라서, '1' 블럭은 1점이고, '4' 블럭은 총 16점 (네 칸에 4가 써있기 때문)이다.

효빈이는 블럭 위에 '1' 블럭을 미리 몇 개 놓았다. 이제, 영선이는 그 위에 '1' 블럭과 '4' 블럭을 놓아서 점수를 최대로 하려고 한다.

왼쪽 그림은 효빈이가 놓은 상태이고, 오른쪽 그림은 점수가 최대가 되게 놓은 방법이다. 이 때, 점수는 4*16 + 6*1 = 70점이다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N ≤ 10, 1 ≤ M ≤ 25)

둘째 줄부터 효빈이가 놓은 보드가 주어진다. '.'은 빈 칸, '1'은 '1' 블럭이 놓여져 있는 칸이다.

출력

첫째 줄에 영선이가 얻을 수 있는 점수의 최대값을 출력한다.

예제 입력

2 11
.....1..1..
..1.....1..

예제 출력

70

예제 입력 2

5 5
...1.
.....
.1..1
.....
1....

예제 출력 2

73

예제 입력 3

4 5
...1.
.1...
..1.1
1....

예제 출력 3

20

예제 입력 4

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

예제 출력 4

117

힌트