Problem E
Rust
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 |
