Alien Journey

Interview

Time limit5sMemory limit2048 MB

Summary

Find the least lift height for an l by l square ship to move from the top-left to the bottom-right corner of a height grid.

Level: Medium6 of 10
Topics: Shortest path, Sliding window, Matrix
Solved: No attempts yet

Problem

A tiny alien asks you for help getting his square spaceship across town to an interdimensional gateway. He has very little fuel, so he needs the minimum amount of power to cross the city. Each unit of fuel lifts the spaceship one unit in height.

The spaceship must fly over every cell beneath it while it moves. It moves north, south, east, or west without using fuel, and the whole ship must stay inside the map at all times.

The ship starts on the ground, and the area it starts on is at height 0. The top-left corner cell of the ship overlays the top-left corner cell of the map, and all four edges of the ship are aligned with the grid. To be above the ground, the bottom of the ship must be strictly higher than the height of every ground cell beneath it. The ship can only be lifted an integer number of units.

The journey ends when the bottom-right corner cell of the ship is floating above the bottom-right corner cell of the map.

The map is a grid of $h$ rows and $w$ columns, and each cell has a height relative to sea level. The spaceship is a square with edge length $l$ , where $1 \leq l < \min(h, w)$ .

Find the minimum amount of fuel the alien needs.

Input

The first line contains three integers $h$ , $w$ , and $l$ with $1 \leq h \leq 500$ , $1 \leq w \leq 500$ , and $1 \leq l < \min(h, w)$ .

Each of the next $h$ lines contains $w$ integers in the range $[0, 10^9]$ . The $j$ -th integer on the $i$ -th line is the height of the cell at row $i$ and column $j$ .

Output

Print the minimum amount of power units the alien needs to traverse the city with the spaceship.

Examples3

Example 1

Input

Expected output

Example 2

Input

6 6 1
0 1 2 3 4 5
0 1 2 3 4 5
0 1 1 1 1 5
0 3 4 5 6 7
0 3 0 0 0 7
0 0 0 1 0 0

Expected output

Example 3
Input
```
3 3 2
0 0 7
0 0 7
9 7 9
```
Expected output
```
10
```