Cave

Interview

Time limit2sMemory limit1024 MB

Summary

Given a grid with walls and rupees, choose a lamp radius L measured by BFS distance from the start to maximize total rupees minus L times C.

Level: Medium4 of 10
Topics: BFS, Prefix sum
Solved: No attempts yet

Problem

Zelda sets out on her first adventure, eager to save the Kingdom of Hyrule, but running around to do so is harder than it sounds. Reality is not kind. To raise funds for the adventure, she has no choice but to focus on collecting rupees (the currency).

One day, Zelda finds a dark cave. Rupees are scattered inside, but it is too dark to see them, so she wants to light the cave with a lamp and collect them. The cave is an $N \times M$ grid. The cell in row $r$ from the top and column $c$ from the left is written $(r,c)$ . Some cells are walls, so Zelda cannot move through them and lamp light cannot pass through them.

The lamp is fixed at the cave entrance $(S_r, S_c)$ , and Zelda cannot carry it while she moves. However, she can freely set the lamp brightness to any non-negative integer $L$ . With brightness $L$ , the lamp lights every cell whose shortest distance from the lamp position is at most $L$ . The shortest distance is the minimum number of cells passed when moving from the start to the target through orthogonally adjacent cells, not counting the starting cell. Zelda collects the rupees on every lit cell, but brightness costs $C$ per unit. If the brightness is set to $L$ , the cost is $L \times C$ .

Let $T$ be the total rupees collected. Zelda's profit is $T-L \times C$ . Find the maximum profit Zelda can earn in the cave.

Input

The first line contains $N$ , $M$ , and $C$ separated by spaces. $(2 \le N,M \le 1000; 1 \le C \le 100)$

The second line contains $S_r$ and $S_c$ separated by a space. $(1 \le S_r \le N; 1 \le S_c \le M)$

The next $N$ lines each contain $M$ integers separated by spaces. Each value is a non-negative integer at most 1000, or $-1$ . A value of $-1$ marks a wall that cannot be passed. Any other value is the number of rupees on that cell. The lamp start cell is never a wall, but it may contain rupees. Every cell outside the grid is a wall, so neither Zelda nor lamp light can pass through it.

Output

Print the maximum profit Zelda can get by adjusting the lamp brightness. If no profit is possible, print $0$ .

Examples2

Example 1

Input

5 5 2
3 3
1 1 0 -1 10
2 -1 5 -1 1
13 -1 0 -1 1
1 -1 -1 1 1
1 1 1 1 1

Expected output

Example 2
Input
```
2 2 2
1 1
0 1
-1 2
```
Expected output
```
0
```