시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 1 1 25.000%

문제

상근이는 집 지하실에서 쥐를 발견했다. 쥐를 끔찍하게 싫어하는 상근이는 지하실에 쥐덫을 많이 설치했다.

지하실은 N*N 그리드로 나타낼 수 있다. 각 칸에는 해당 칸에 설치되어 있는 쥐덫의 개수가 저장되어 있다. 모든 칸에는 적어도 1개의 쥐덫이 있다.

신기하게도 정인이도 집 지하실에서 쥐를 발견했다. 하지만, 마을의 모든 쥐덫은 상근이가 모두 구매했기 때문에, 정인이는 살 수 있는 쥐덫이 없다. 어쩔수없이 정인이는 상근이에게 쥐덫을 빌려오려고 한다.

상근이와 정인이는 쥐덫에 대한 30분 동안 토론을 하였고, 상근이네 지하실의 쥐덫을 일부 제거해서 정인이에게 주기로 결정했다. 좀 더 자세하게 설명하자면 각각의 줄에 대해서, 연속된 K개의 칸을 선택한다. 그 뒤 선택한 칸에 있는 쥐덫을 모두 제거한 뒤 정인이에게 전달해 준다.

이렇게 쥐덫을 제거한 뒤에는 쥐는 상근이네 지하실의 왼쪽벽에서 오른쪽벽으로, 위쪽벽에서 아래쪽벽으로 지나갈 수 없어야 한다. 쥐는 4방향(위, 아래, 왼쪽, 오른쪽)으로 이동할 수 있고, 쥐덫이 하나도 없는 칸만 지나갈 수 있다.

위의 조건을 지키면서 상근이의 지하실에서 제거할 수 있는 쥐덫의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 250, 1 ≤ K ≤ N/2) N은 지하실의 크기, K는 각각의 줄에서 제거해야 하는 연속된 칸의 개수이다.

출력

첫째 줄에 상근이의 집에서 제거할 수 있는 쥐덫의 최대 개수를 출력한다.

예제 입력

4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1

예제 출력

36

힌트