시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB52312554.348%

문제

유토는 X 칠하기 게임을 하려고 한다. X 칠하기 게임은 $N\times N$ 격자의 칸을 칠하는 게임이다. 처음에 각 칸은 비어 있으며, 플레이어는 적당히 칸들을 골라 색칠할 수 있다. 이때, 색칠된 두 칸이 서로 인접할 수 없다.

게임의 점수는 다음과 같이 결정된다.

  • 격자의 $i$행 $j$열에 해당하는 칸을 $(i, j)$라고 하자. $(i, j)$를 색칠한 경우 $A_{ij}$ 점을 받는다. 이때, $A_{ij}$가 음수일 수도 있다. 이 경우 해당 칸을 색칠하면 점수를 잃음을 의미한다.
  • 격자에서 발견할 수 있는 X 모양 하나당 $K$점을 받는다.

여기서, X 모양은 다음 그림과 같은 모양을 의미한다. 즉, $(i-1,j-1)$, $(i-1,j+1)$, $(i,j)$, $(i+1,j-1)$, $(i+1,j+1)$ 이 모두 칠해진 $(i,j)$ 쌍 하나마다 $K$점을 얻는다.

이때 유토가 받을 수 있는 최대 점수를 구해보자!

입력

첫 번째 줄에 격자판의 크기를 의미하는 $N$, $K$가 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 걸쳐, 각 칸을 색칠하면 얻을 수 있는 점수 $A_{ij}$ 가 주어진다.

출력

유토가 받을 수 있는 최대 점수를 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $1\le N\le 50$
  • $1\le K\le 10$
  • $-10\le A_{ij}\le 10$

예제 입력 1

3 1
10 -5 7
-2 -2 8
-2 -6 6

예제 출력 1

23

예제 입력 2

3 4
10 6 7
-2 -2 8
-1 -6 6

예제 출력 2

24

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final G번