동물 관찰 (쉬운 버전)

쉬운 버전과 어려운 버전의 차이는 $k$의 제약 조건뿐이다.

Gildong은 동물 관찰을 좋아해서 숲에서 야생동물을 촬영하려고 카메라를 두 대 샀다. 한 대는 빨간색이고 다른 한 대는 파란색이다.

Gildong은 1일부터 $n$일까지 $n$일 동안 영상을 찍는다. 숲은 1번부터 $m$번까지 번호가 붙은 $m$개의 구역으로 나뉜다. 카메라는 다음과 같이 사용한다.

• 홀수 날(1일, 3일, 5일, ...)에는 빨간 카메라를 숲에 가져가 2일 동안 영상을 찍는다.
• 짝수 날(2일, 4일, 6일, ...)에는 파란 카메라를 가져가 2일 동안 영상을 찍는다.
• $n$일째에 카메라로 촬영을 시작하면 그 카메라는 하루만 촬영한다.

카메라 하나는 연속된 $k$개 구역을 관찰할 수 있다. 예를 들어 $m=5$, $k=3$이면 카메라를 $[1,3]$, $[2,4]$, $[3,5]$ 중 하나에 두고 이틀 동안 관찰할 수 있다.

Gildong은 날마다 구역별로 볼 수 있는 동물 수를 알고 있다. 최대한 많은 동물을 관찰하려고 하므로, $n$일 동안 두 카메라를 배치하는 최선의 방법을 찾아야 한다. 두 카메라가 같은 날 같은 구역을 관찰하면, 그 구역의 동물은 한 번만 센다.

첫 줄에는 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 50$, $1 \le m \le 2 \cdot 10^4$, $1 \le k \le \min(m,20)$). 각각 기록하는 날의 수, 구역의 수, 카메라가 관찰하는 연속 구역의 수이다.

다음 $n$개 줄에는 각각 $m$개의 정수가 주어진다. $i+1$번째 줄의 $j$번째 정수는 $i$일째에 $j$번 구역에서 볼 수 있는 동물 수이며, 0 이상 1000 이하이다.

관찰할 수 있는 동물 수의 최댓값을 한 줄에 정수로 출력한다.

네 테스트 케이스에서 동물을 관찰하는 최적의 방법은 다음 그림과 같다.

테스트 1:

테스트 2:

테스트 3:

테스트 4: