시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB88515064.103%

문제

덴지는 $16$년 동안 나무 조각상을 깎아 온 목공의 고수이다. 덴지는 최근 전기톱을 사용해 조각을 하는 것을 시도해 보았다.

전기톱 조각을 하기 위해서는 재료로 직사각형 모양의 통나무가 필요하고, 아래 그림 중 왼쪽은 덴지가 방금 가져온 $4\times 5$ 크기의 통나무이다. 덴지는 전기톱만을 사용해 이 통나무를 오른쪽과 같은 모양으로 조각해 의자를 만들었다.

자신이 만든 작품이 마음에 들었던 덴지는 또 다른 조각을 만들어 보기로 했다. 덴지는 세로 $N$, 가로 $M$의 직사각형 모양의 통나무를 새로 가져와서 이 통나무가 처음에 있는 $N \times M$의 영역을 작업 영역으로 두고, 한 변의 길이가 $1$인 정사각형 $N \times M$개로 만들어진 격자를 작업 영역에 완전히 포함되게 만들었다.

덴지는 격자 내의 정사각형들로 나타낼 수 있는 모양을 정해서 이 모양과 일치하는 조각을 완성하기로 했고, 두 가지 방법만으로 전기톱을 사용하며 소모하는 힘의 합을 최소화하기로 했다.

전기톱을 사용하는 첫 번째 방법은 격자를 이루는 정사각형의 꼭짓점에서 시작해 반직선 형태로 격자를 따라 나무를 자르는 것이다. 이 방법으로 나무를 자르게 되면 작업 영역을 벗어나기 전까지는 멈출 수 없고, 움직인 거리와 상관없이 $F$ 만큼의 힘이 소모된다. 그림의 주황색 화살표를 참고해도 좋다.

두 번째 방법은 격자를 이루는 정사각형의 꼭짓점에서 시작해 격자를 따라 길이 $l$의 선분 형태로 나무를 자르는 것이다. 첫 번째 방법과는 달리 $l$이 정수가 되는 한 원하는 때에 멈출 수 있고, 길이 $l$의 선분 형태로 자르는 데에는 $l$ 만큼의 힘이 소모된다. 그림의 검은색 화살표를 참고해도 좋다.

덴지는 조각의 어떤 부분도 회전시키거나 이동시키지 않을 것이고, 조각을 끝낸 후 격자에 포함되는 정사각형 중 완성해야 하는 조각에 포함되는 두 정사각형 사이에 톱질이 되어있으면 안되며, 완성해야 하는 조각에 포함되는 정사각형과 포함되지 않는 정사각형 사이에는 반드시 톱질이 되어있어야 한다. 완성해야 하는 조각에 포함되지 않는 정사각형 둘 사이에는 톱질이 되어있는지 상관하지 않는다. 예를 들어, 덴지는 아래와 같은 모양의 조각을 만들 때 화살표와 같은 톱질을 할 수 있다.

통나무의 가로와 세로의 길이와 조각해야 하는 모양이 주어졌을 때, 덴지가 조각을 완성하기 위해 소모해야 하는 힘의 최솟값을 구하시오.

입력

첫 줄에 통나무 세로의 길이 $N$, 가로의 길이 $M$과 첫 번째 방법으로 나무를 자를 때 소모되는 힘 $F$가 주어진다. ($1\le N,M,F\le 80$)

다음 줄부터 $N$개의 줄에 한 줄에 하나씩 완성해야 하는 조각의 모양을 나타내는 #.로만 이루어진 길이 $M$의 문자열이 $N$개 주어진다.

각 문자는 작업 영역의 격자가 되는 정사각형을 뜻하고, #는 나무가 존재하는 격자, .는 나무가 존재하지 않는 격자를 의미한다.

입력에는 하나 이상의 #가 존재한다.

출력

덴지가 조각을 완성하기 위해 소모해야 하는 힘의 최솟값을 출력한다.

예제 입력 1

4 5 1
#....
#....
#####
#...#

예제 출력 1

7

예제 입력 2

9 9 2
.........
.........
...###...
..#####..
..##.##..
..#####..
...###...
.........
.........

예제 출력 2

20

예제 입력 3

4 6 2
.....#
##...#
##.##.
...##.

예제 출력 3

12

출처

Contest > BOJ User Contest > 아니메컵 > 아니메컵 2쿨 D번