# Problem H

Sjön Sjön Cleanup

The water in LTH’s own lake *sjön Sjön*
has for millennia been a source of intense disgust. Now, in
preparation for next years nollning, an attempt will be made to
clean up the water in sjön Sjön by pouring a special cleaning
solution into the lake.

The area around sjön Sjön can be modeled as a two dimensional grid where each cell is either water or land. Wind conditions cause the water in each water cell to flow in one of the four cardinal directions: north, south, east or west.

There may be islands in sjön Sjön, which are made up of land cells that are not connected to the edge of the grid by other land cells. All cells at the edge of the grid are land cells, and a land cell is only directly connected to its four immediate neighbors (not its four diagonal neighbors).

The cleaning solution will be poured into sjön Sjön from
various points along the lake’s shoreline. This means that the
solution can only be poured into water cells that have at least
one **non-island** land cell among its four
immediate neighbors.

Once poured into the lake, the cleaning solution will follow the flow of the water and clean the first $S$ water cells it enters (including the cell which the solution was initially poured into). Following the flow of the water means that solution repeatedly moves into the neighboring cell which the water in the current cell flows towards. If the solution reaches a land cell it stops moving.

Given the map of sjön Sjön, help the LTH students to minimize the number of shoreline cells that they need to pour cleaning solution into, while still making sure that every water cell in sjön Sjön becomes cleaned.

## Input

The first line contains three integers $N$, $M$, and $S$ ($3 \leq N, M \leq 1000$, $1 \leq S \leq 10^9$), the number of rows and columns of the map, and the number of water cells the solution travels.

The following $N$ lines
contain a map of Sjön-Sjøn. Each line consists of $M$ characters, each one of which is
either “`#`”, “`<`”, “`>`”,
“`^`” or “`v`”. These represent land, water
flowing west, water flowing east, water flowing north and water
flowing south respectively. Lines are given from northernmost
to southernmost, and characters within a line are given from
westernmost to easternmost.

## Output

Output the minimum number of cells that need to have
cleaning solution poured into them in order to clean all of
sjön Sjön, or “`impossible`” if it’s impossible to clean
all of sjön Sjön no matter how many cells receive cleaning
solution.

## Scoring

Group |
Points |
Constraints |
Satisfied by Sample Input(s) |

$1$ |
$15$ |
$N = 3$ |
$1$ |

$2$ |
$15$ |
$S = 10^9$ |
$4$ |

$3$ |
$20$ |
There is no grid cell where the water flows north
( |
$1$, $2$ and $5$ |

$4$ |
$20$ |
$N,M \leq 80$ |
All sample inputs |

$5$ |
$30$ |
No further constraints |
All sample inputs |

## Sample Description

Sample Input 1 | Sample Output 1 |
---|---|

3 11 3 ########### #>>>><<#v<# ########### |
3 |

Sample Input 2 | Sample Output 2 |
---|---|

6 6 3 ###### ##v<v# #v<#v# #v#v<# #><<## ###### |
5 |

Sample Input 3 | Sample Output 3 |
---|---|

17 14 5 ############## ###########v^# ########v<<>^# ########>v^<## #######>^>^^## ######>^v<<<## #####>>vvv<<<# ####>v>v>v><<# ####v>^>^<<<## ###vv><<<<<### ###v>^#<v<#### ###>v##^><#### ##>v>>>^<##### ##^>>><<<##### #>>>v^<<###### #^<<>>>>###### ############## |
22 |

Sample Input 4 | Sample Output 4 |
---|---|

17 14 1000000000 ############## ###########v^# ########v<<>^# ########>v^<## #######>^>^^## ######>^v<<<## #####>>vvv<<<# ####>v>v>v><<# ####v>^>^<<<## ###vv><<<<<### ###v>^#<v<#### ###>v##^><#### ##>v>>>^<##### ##^>>><<<##### #>>>v^<<###### #^<<>>>>###### ############## |
18 |

Sample Input 5 | Sample Output 5 |
---|---|

5 7 2 ####### ##>>vv# #v#v<v# #>>><<# ####### |
impossible |