E. Just Passing Through
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Justin and Fred are taking a road trip, traveling from West to East across their state. They have a few Road Trip Rules:

  1. They must have an awesome time!
  2. The trip must begin somewhere along the Western edge of the state and finish somewhere along the Eastern edge of the state.
  3. Each step in their trip must move them either directly East, diagonally Northeast, or diagonally Southeast.
  4. They want to travel through exactly $$$n$$$ "passes" (defined below).
  5. Due to Fred's sensitivity to higher elevations, they wish to minimize the cumulative sum of elevations during the trip.
  6. They must have an awesome time!
Because Justin and Fred are traveling Eastward, a "pass" is any location with strictly lower elevations to its East and West and strictly higher elevations to its North and South. Consider the elevation map shown in Figure 1. Undrivable locations (either due to water or stubborn insistence on staying in-state) are shown in black, while passes are shown as gray. Locations adjacent to the border or to undrivable locations are not eligible for considerations as passes.
Figure 1: A sample elevation map.
Input

The input begins with three integers $$$r$$$ $$$c$$$ $$$n$$$ representing the number of rows and columns in the representation of the state's topography ($$$3 \leq r, c \leq 500$$$) and the exact number of passes to be crossed ($$$0 \leq n \leq 10$$$). The next $$$r$$$ lines each contain $$$c$$$ elevation entries. Undrivable locations are represented by $$$-1$$$, and all other elevations are between $$$0$$$ and $$$1\, 000$$$. There is guaranteed to be at least one drivable location on both the Eastern and Western borders.

Output

Output the sum of the elevations along the optimal path which satisfies the Road Trip Rules. If no such path exists, output impossible.

Examples
Input
5 7 2
-1 -1 2 5 4 3 1
3 4 1 4 1 2 1
3 4 5 5 3 4 5
2 3 2 1 2 3 2
-1 5 4 1 4 4 2
Output
14
Input
4 3 1
3 4 5
2 4 2
1 5 4
1 1 1
Output
impossible