Problem R
Rust

Mynd fengin af commons.wikimedia.org

Benni er nýbyrjaður að spila leikinn Rust. Þetta er gífurlega spennandi leikur fullpakkaður af hasari. Í Rust er samt líka hægt að byggja. Benni er búinn að vera allan dag að safna steinum til að geta búið til sitt eigið heimili. Hann hefur ákveðið að búa til ferningslaga múr að stærð $K \times K$.

Benni gerði sér aldrei grein fyrir því að það yrði erfitt að velja stað til að búa til heimilið sitt. Benni hefur kort af stærð $N \times N$. Á því má sjá steina sem ekki er hægt að brjóta og eru þeir táknaðir sem # á kortinu. Einnig eru verðmæti á kortinu en þau eru táknuð með tölu á bilinu $1$ til $9$. Ef Benni ákveður að byggja þennan ferningslaga múr sinn þá má ekki vera neinn óbrjótanlegur steinn á svæðinu sem múrinn verður byggður á né verðmæti. Hinsvegar má múrinn liggja utan um óbrjótanlega steina eða verðmæti. Ef Benni býr til múr sem umlykur verðmæti þá mun hann eignast öll verðmætin sem eru innan fyrir múrinn.

Benni hefur ekki hugmynd hvar hann ætti að byggja múrinn sinn. Hann spyr þig hvort þú getir sagt honum hvað mesta virði samanlagðra verðmæta væri sem hann gæti átt ef hann myndi byggja múrinn sinn á sem besta stað.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $N$ ($5 \leq N \leq 1\, 000$), stærð kortsins, og $K$ ($3 \leq K \leq N$), stærð múrsins sem Benni ætlar að byggja.

Næst koma $N$ línur, hver lína hefur $N$ stök. Á kortinu má sjá #, sem táknar óbrjótanlega steina, . sem táknar tóman reit og einnig má sjá tölur á bilinu $1$ til $9$ sem tákna verðmæti, þar sem talan táknar hversu mikils virði þetta verðmæti er.

Úttak

Skrifa skal út eina tölu, mesta virði samanlagðra verðmæta sem Benni gæti átt ef hann byggir múrinn sinn á sem besta stað. Ef enginn staður kemur til greina, þá skal skrifa út töluna $0$.

Stigagjöf

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

5

5 5
.....
.333.
.333.
.333.
.....

27

5 5
....#
.333.
.333.
.333.
.....

0