Description
Elfnt just walked into an all-you-can-eat vegan buffet, represented by an grid. Each cell holds a food tray with a certain amount of fresh salad leaves. Initially, Elfnt starts at position (0-indexed) and is eager to eat as much as possible!
Elfnt can smell trays within a Manhattan distance of at most from his current position. He greedily eats according to the following rules:
- Elfnt completely cleans out the salad tray at his current position, adding its leaves to his total. The amount of leaves at this cell then becomes
0(indicating an empty plate). - He sniffs around and moves to the tray within Manhattan distance that has the greatest amount of leaves. If all reachable trays within distance contain
0leaves, Elfnt stops moving and eating immediately.
Note:
- The Manhattan distance between two cells and is defined as .
Input
The first line contains three integers , , and — the number of rows, the number of columns, and the maximum Manhattan distance Elfnt can smell.
The next lines each contain integers, representing the initial amount of leaves on each tray.
The last line contains two integers and , representing Elfnt's starting row and column coordinates.
Constraints
- The initial amount of leaves on any tray satisfies .
- All non-zero leaf amounts are guaranteed to be distinct (i.e., except for trays with
0leaves, all leaf values across the buffet are unique).
Output
Output a single integer representing the total amount of salad leaves Elfnt consumes before he stops, followed by a new line.