어둠 막기

보건 안전을 이유로 모든 나이트클럽이 최소 조도 기준을 지켜야 한다. 시는 클럽 바닥을 한 변이 1미터인 정사각형 칸으로 나누고, 각 칸의 중심에 계측기를 놓아 조도를 잰다.

클럽 주인은 조명을 새로 달 생각이 없다. 대신 기준에 못 미치는 어두운 칸을 투명 칸막이로 막아 두고 나중에 처리하려고 한다.

클럽의 조명 배치가 $R \times C$ 격자로 주어진다. 칸 $(r, c)$의 중심 바로 위 천장에 세기가 $s$인 전구가 하나 달려 있고, $s$는 0 이상 9 이하의 정수다. $s$가 0이면 그 칸 위에는 전구가 없다. 천장은 평평해서 높이가 어디서나 $H$로 같다.

전구 하나는 클럽의 모든 칸에 빛을 보낸다. 전구에서 계측기까지의 변위가 $(x, y, z)$이면 그 칸의 조도가 다음만큼 올라간다.

$\frac{s}{x^2 + y^2 + z^2}$

칸 $(r, c)$의 조도는 모든 전구가 그 칸에 더하는 값의 합이다. 칸 $(r', c')$ 위 전구에서 칸 $(r, c)$의 계측기까지의 변위는 $(|r - r'|, |c - c'|, H)$다. 조도가 $B$ 이상인 칸은 기준을 만족하고, $B$보다 낮은 칸은 어둡다.

칸막이는 이웃한 두 칸이 맞닿은 변에 한 장씩 세운다. 두 칸 중 적어도 하나가 어두우면 한 장에 11파운드가 든다. 두 칸이 모두 기준을 만족하면 번쩍이는 클럽 조명 아래에서 작업하기 힘들다며 인부가 수당을 더 요구해서, 한 장에 43파운드가 든다.

막아 둘 칸의 집합 $S$를 고른다. $S$는 어두운 칸을 모두 포함해야 하고, 테두리 칸은 하나도 포함할 수 없다. 테두리 칸은 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 칸이다. $S$에 속한 칸과 $S$에 속하지 않은 이웃 칸이 맞닿은 변마다 칸막이를 한 장 세운다. 클럽 바깥벽은 이미 있어서 칸막이가 필요 없다. $S$는 여러 조각으로 나뉘어도 되고, 기준을 만족하는 칸을 함께 감싸도 된다.

어두운 칸을 모두 막는 데 드는 최소 비용을 구하라.

• 첫째 줄에 최소 조도 기준 $B$가 주어진다. ($0 < B \le 9$)
• 둘째 줄에 천장 높이 $H$가 주어진다. ($0 < H \le 5$)
• 셋째 줄에 클럽의 세로 칸 수 $R$과 가로 칸 수 $C$가 공백으로 구분되어 주어진다. ($0 < R, C \le 30$)
• 다음 $R$개 줄에는 길이가 $C$인 숫자 문자열이 한 줄씩 주어진다. $r$번째 줄의 $c$번째 숫자는 칸 $(r, c)$ 위 전구의 세기다.

입력으로 주어지는 값은 모두 정수다. 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 테두리 칸은 모두 기준을 만족한다.

칸막이에 드는 최소 비용을 파운드 단위 정수 하나로 출력한다.