# Problem A

Rust

Languages
en
is
Benni has just started playing the game Rust. This is an extremely exciting game full of action. But in Rust you can also build. Benni has been collecting rocks all day so he can build his own home. He has decided to build a square wall with dimensions $K \times K$.

Benni never realized how hard it would be to pick a spot for
his home. Benni has a map with dimensions $N \times N$. There are static rocks
which are unbreakable marked on the map with `#`. Additionally, there are valuables marked on
the map with the digits $1$ to $9$. Benni cannot build a wall on
rocks or valuables. However, the hollow area within the wall
can include rocks and valuables. If Benni builds a wall
surrounding some amount of valuables then he gains possession
of those valuables.

Benni has no idea where he should build his wall. He asks if you can tell him where to build his wall to maximize the total worth of valuables he can possess.

## Input

The first line of the input contains two integers $N$ ($5 \leq N \leq 1\, 000$), the dimensions of the map, and $K$ ($3 \leq K \leq N$), the dimensions of the wall.

Then $N$ lines follow,
each with $N$ symbols,
representing the map. It includes `#`,
representing unbreakable rocks, `.`,
representing empty tiles and digits between $1$ and $9$ which represent valuables, in
particular, their value.

## Output

Output a single integers, the maximum total value of the valuables Benni can gain possession of, assuming he builds his wall in the optimal spot. If there is no spot for Benni to build his home then output $0$.

## Scoring

Group |
Points |
Constraints |

1 |
23 |
$K = 3$ |

2 |
27 |
$N \leq 50$ |

3 |
50 |
No further constraints. |

Sample Input 1 | Sample Output 1 |
---|---|

5 3 ..... .5.7. ...#. .9... 2.... |
5 |

Sample Input 2 | Sample Output 2 |
---|---|

5 5 ..... .333. .333. .333. ..... |
27 |

Sample Input 3 | Sample Output 3 |
---|---|

5 5 ....# .333. .333. .333. ..... |
0 |