Clap in a Row

Interview

Time limit2sMemory limit1024 MB

Summary

Given an N by M grid of clap counts, find the largest total clap count over any A consecutive columns spanning all rows.

Level: Easy3 of 10
Topics: Prefix sum, Sliding window, Array
Solved: No attempts yet

Problem

Today is the day of the school festival that many students have been waiting for. As the festival coordinator, Bsil placed chairs in $N$ rows and $M$ columns in front of the stage, with one cheering squad member seated on each chair.

Bsil wants to check the cheering squad's morale by finding the spot with the most claps among $A$ consecutive columns. For columns 1 to $A$ , 2 to $A+1$ , 3 to $A+2$ , $\cdots$ , and $M-A+1$ to $M$ , every member in the range claps. Then the largest clap count among these ranges is found.

Bsil has many duties as the festival coordinator, so Bsil left this job to us and went off to do other work.

Given the number of claps by each cheering squad member, find the clap count of the range that received the most claps.

Input

The first line contains integers $N$ and $M$ separated by a space. $(1 \le N,M \le 2\,000)$

The next $N$ lines describe the clap counts. Line $i+1$ contains $Q_{i,1}, Q_{i,2}, \cdots, Q_{i,M}$ separated by spaces, where $Q_{i,j}$ is the clap count of the member in row $i$ , column $j$ . $(1 \le Q_{i,j} \le 500)$

Line $N+2$ contains $A$ , the number of columns chosen by Bsil. $(1 \le A \le M)$

Output

Print the clap count of the range that received the most claps.

Examples3

Example 1
Input
```
3 4
1 5 2 6
2 3 1 5
1 2 1 1
2
```
Expected output
```
16
```
Example 2
Input
```
1 5
1 3 2 5 4
3
```
Expected output
```
11
```
Example 3
Input
```
5 1
2
3
4
5
6
1
```
Expected output
```
20
```