Rust

commons.wikimedia.org에서 가져온 이미지

Benni는 이제 막 Rust라는 게임을 시작했다. 이 게임은 액션으로 가득한 매우 흥미진진한 게임이다. 하지만 Rust에서는 건축도 할 수 있다. Benni는 자신만의 집을 만들기 위해 온종일 돌을 모았다. 그는 크기가 $K \times K$인 정사각형 모양의 벽을 만들기로 했다.

Benni는 자신의 집을 지을 장소를 고르는 일이 어려울 줄은 전혀 몰랐다. Benni에게는 크기가 $N \times N$인 지도가 있다. 지도에는 부술 수 없는 바위가 표시되어 있으며, 이는 지도에서 #로 나타난다. 또한 지도에는 귀중품이 있으며, 이는 $1$부터 $9$ 사이의 수로 나타난다. Benni가 이 정사각형 모양의 벽을 짓기로 한다면, 벽이 세워지는 영역에는 부술 수 없는 바위도 귀중품도 있어서는 안 된다. 하지만 벽이 부술 수 없는 바위나 귀중품을 둘러싸는 것은 허용된다. Benni가 귀중품을 둘러싸는 벽을 만들면 벽 안에 있는 모든 귀중품을 얻게 된다.

Benni는 벽을 어디에 지어야 할지 전혀 모른다. 그는 벽을 가장 좋은 위치에 지었을 때 자신이 얻을 수 있는 귀중품의 가치 합계의 최댓값이 얼마인지 알려 달라고 부탁한다.

점수

그룹 | 점수 | 제한

1 | 23 | $K = 3$

2 | 27 | $N \leq 50$

3 | 50 | 추가 제한 없음

입력의 첫 번째 줄에는 두 정수 $N$와 $K$ ($5 \leq N \leq 1\,000$, $3 \leq K \leq N$)가 주어지며, 각각 지도의 크기와 Benni가 지으려는 벽의 크기를 나타낸다.

다음 $N$개의 줄에는 각각 $N$개의 원소가 주어진다. 지도에는 부술 수 없는 바위를 나타내는 #, 빈 칸을 나타내는 ., 그리고 귀중품을 나타내는 $1$부터 $9$ 사이의 수가 표시되며, 이 수는 해당 귀중품의 가치를 나타낸다.

Benni가 벽을 가장 좋은 위치에 지었을 때 얻을 수 있는 귀중품의 가치 합계의 최댓값을 하나의 수로 출력한다. 가능한 위치가 없다면 $0$을 출력한다.