14389번 - 4블록

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' 블록이 놓여져 있는 칸이다.

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