줄줄이 박수

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N행 M열 표에서 연속된 A개 열을 골랐을 때, 그 안 박수 횟수의 합이 가장 큰 값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 슬라이딩 윈도우, 배열
정답자: 아직 제출이 없습니다

문제

오늘은 많은 학생이 기다리던 브실브실 학교의 축제 날이다. 브실이는 학교 축제 담당자로서 축제 분위기가 잘 살아나도록 무대 앞에 $N$ 행 $M$ 열로 의자를 놓고, 각 의자에 응원단 사람을 1명씩 앉혀 두었다.

브실이는 응원단의 사기를 확인하려고 연속된 $A$ 개 열 중에서 박수 횟수가 가장 많은 곳을 찾으려 한다. 즉, $1$ 열부터 $A$ 열, $2$ 열부터 $A+1$ 열, $3$ 열부터 $A+2$ 열, $\cdots$ , $M-A+1$ 열부터 $M$ 열까지 각 구간에 속한 응원단 사람들이 박수를 치게 한 뒤, 그중 가장 많이 박수를 친 구간의 박수 횟수를 찾는다.

하지만 브실이는 축제 담당자로서 할 일이 많아 이 일을 우리에게 맡기고 다른 일을 하러 갔다.

각 응원단 사람이 박수를 치는 횟수가 주어졌을 때, 가장 많이 박수를 친 구간의 박수 횟수가 몇 회인지 구하시오.

입력

첫 번째 줄에 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. $(1 \le N,M \le 2\,000)$

두 번째 줄부터 $N$ 개의 줄에 걸쳐 박수 횟수에 대한 정보가 주어진다. $i+1$ 번째 줄에는 $i$ 행 1열부터 $i$ 행 $M$ 열까지 그 자리에 있는 응원단 사람의 박수 횟수 $Q_{i,1}, Q_{i,2}, \cdots, Q_{i,M}$ 이 공백으로 구분되어 주어진다. $(1 \le Q_{i,j} \le 500)$

$N+2$ 번째 줄에는 브실이가 정한 열의 개수 $A$ 가 주어진다. $(1 \le A \le M)$

출력

가장 많이 박수를 친 구간의 박수 횟수를 출력한다.

예제3

예제 1
입력
```
3 4
1 5 2 6
2 3 1 5
1 2 1 1
2
```
예상 출력
```
16
```
예제 2
입력
```
1 5
1 3 2 5 4
3
```
예상 출력
```
11
```
예제 3
입력
```
5 1
2
3
4
5
6
1
```
예상 출력
```
20
```