Fencing off the darkness

For health and safety reasons every night club now has to meet a minimum lighting standard. The city divides the club floor into squares of one metre by one metre and measures the light level with a probe at the centre of each square.

The club owner will not install new lighting. The owner will fence off the dark squares with transparent panels instead and deal with them later.

The lighting layout of the club is given as an $R \times C$ grid. Directly above the centre of square $(r, c)$ there is one bulb of strength $s$, where $s$ is an integer from 0 to 9. If $s$ is 0 there is no bulb above that square. The ceiling is flat, so its height is $H$ everywhere.

Every bulb sends light to every square of the club. If the displacement from a bulb to a probe is $(x, y, z)$, the light level at that square rises by

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

The light level of square $(r, c)$ is the sum of what every bulb adds to it. The displacement from the bulb above square $(r', c')$ to the probe of square $(r, c)$ is $(|r - r'|, |c - c'|, H)$. A square whose light level is at least $B$ meets the standard, and a square below $B$ is dark.

A panel of fencing is built on the shared edge of two adjacent squares. One panel costs 11 pounds when at least one of the two squares is dark. When both squares meet the standard the builders demand extra pay for working under the flashing club lights, so one panel costs 43 pounds.

You pick the set $S$ of squares to fence off. $S$ has to contain every dark square and cannot contain any border square. The border squares are the ones in the first row, the last row, the first column and the last column. One panel is built on every edge between a square in $S$ and an adjacent square outside $S$. The outer wall of the club already exists and needs no panel. $S$ may come in several pieces, and it may enclose squares that meet the standard.

Find the smallest amount that fencing off every dark square can cost.

• The first line contains the minimum required light level $B$. ($0 < B \le 9$)
• The second line contains the height of the ceiling $H$. ($0 < H \le 5$)
• The third line contains the number of rows $R$ and the number of columns $C$ of the club, separated by a space. ($0 < R, C \le 30$)
• Each of the next $R$ lines contains a string of $C$ digits. The $c$-th digit on the $r$-th line is the strength of the bulb above square $(r, c)$.

Every value in the input is an integer. Every border square, that is every square in the first row, the last row, the first column and the last column, meets the standard.

Print one integer, the smallest number of pounds that has to be spent on fencing.