Hop Game

Interview

Time limit1sMemory limit256 MB

Summary

Start in row 1 of an N x M grid and jump to later rows within Manhattan distance D, multiplying the two cells' values and adding to the score; maximize the total when reaching row N.

Level: Medium7 of 10
Topics: Dynamic programming, Implementation, Math
Solved: No attempts yet

Problem

Taegyun made a fun game that anyone can play with just chalk and a floor.

Draw an N×M rectangular grid on the floor, write an integer in each cell, and play the game by the following rules.

Choose any cell in row 1 and start there.
The game ends when you arrive at any cell in row N.
To move from one cell to another, you may only move to a cell with a larger row number, and the distance between the cells must be at most D. That is, to move from row R, column C to row P, column Q, the condition P > R and | P - R | + | Q - C | ≤ D must hold.
The score starts at 0, and each move from one cell to another multiplies the numbers in the two cells and adds the product to the current score.

Given the numbers written in the cells, find the maximum score you can achieve in the game.

Input

The first line gives the number of rows N, the number of columns M (2 ≤ N×M ≤ 200,000, 2 ≤ N), and the maximum jump distance D (1 ≤ D ≤ 10).

The i+1-th line gives the integers ai,1, ai,2, ..., ai,m (-100 ≤ ai,j ≤ 100) written in row i (1 ≤ i ≤ N) in order.

Output

Print the maximum score you can achieve in the game on the first line.

Examples3

Example 1
Input
```
4 3 2
3 -5 4
2 0 0
1 -3 1
-2 9 1
```
Expected output
```
21
```
Example 2
Input
```
2 2 2
100 100
-100 -100
```
Expected output
```
-10000
```

Example 3

Input

6 6 3
1 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 1 0

Expected output