인류의 적 모기 퇴치

NYPC 2023 · Round 1 연습문제

최근 이상 기후로 인해 붐힐 마을에 모기가 많이 늘어났다. 마리드는 붐힐 마을 주민들을 돕기 위해 물풍선으로 모기들을 퇴치하려고 한다. 마리드는 기존의 십자 모양의 물풍선만으로 모기를 효율적으로 퇴치할 수 없다는 것을 깨달았고, 엑스 자 모양으로 터지는 물풍선을 새로 개발했다.

붐힐 마을은 N×NN \times N 크기의 22차원 배열로 표현할 수 있고, 배열의 각 칸에 존재하는 모기의 수가 주어진다.

마리드는 한 칸을 선택하여 물풍선을 놓고 터트린다. 물풍선을 터트리면 범위 MM으로 물줄기가 뻗어나가 모기를 퇴치할 수 있다. 예를 들어, 십자 모양의 경우, 물풍선을 터트린 칸에서 위쪽, 오른쪽, 아래쪽, 왼쪽의 MM 개 칸 이내의 모든 모기를 퇴치한다. 엑스 자 모양의 경우, 네 개의 대각선 방향으로 MM 개 칸 이내의 모든 모기를 퇴치한다.

마리드가 물풍선을 놓는 칸은 마을 안에 있어야만 하지만, 물풍선이 터지는 물줄기가 마을 밖으로 나가는 경우는 허용된다.

위에서 왼쪽 그림은 M=3M = 3일 때 십자 모양의 물풍선이 터져 나오는 물줄기를 보여주고, 오른쪽 그림은 M=3M = 3일 때 엑스 자 모양의 물풍선이 터져 나오는 물줄기를 보여준다.

십자 모양 혹은 엑스 자 모양의 물풍선을 한 개 터트릴 때, 퇴치할 수 있는 모기 수의 최댓값을 계산하는 프로그램을 작성하시오.

입력 형식

첫 줄에 붐힐 마을의 크기를 나타내는 정수 NN과 물풍선의 범위를 나타내는 정수 MM이 공백으로 구분되어 주어진다. (1N50;1 \le N \le 50; 0M500 \le M \le 50)

이어지는 NN 개 줄의 ii 번째 줄에는 붐힐 마을을 나타내는 배열의 ii 번째 행의 NN 개의 칸에 존재하는 모기의 수를 나타내는 정수 NN 개가 공백으로 구분되어 순서대로 주어진다. 이때, 주어지는 정수는 00 이상 100100 이하이다.

출력 형식

첫 줄에 십자 모양 혹은 엑스 자 모양의 물풍선을 한 개 터트릴 때, 퇴치할 수 있는 모기 수의 최댓값을 출력한다.

예제 1

입력

3 1 1 2 1 2 2 2 1 2 1

출력

10

예제 2

입력

5 2 2 18 6 2 3 5 11 9 12 5 7 21 13 19 6 8 4 1 24 1 7 3 5 7 3

출력

104

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 23

M=0M = 0

종류 2: 61

M=1M = 1

종류 3: 116

추가적인 제한 조건이 없음.

해설