407958: GYM102948 H Jungle Escape

This was supposed to be a fun, wilderness adventure. With an area map and the legendary Bear Grylls as your guide, even a trip deep into the jungle was set to be a casual test of your survival skills and nothing more. That was, until you woke up on the second night with Bear Grylls nowhere to be found.

You frantically remember what Bear told you about the importance of finding potable water and how long you can survive without it. With a conveniently packed TI-84 calculator, you scramble to write a program that can calculate your optimal surviving escape route, else you may fall victim to the ruthlessness of the jungle...

The first line of input contains two integers $$$K$$$ and $$$S$$$, where $$$1 \leq K \leq 10^3$$$ and the ratio $$$S/K \leq 100$$$. The value $$$K$$$ is the number of hours required to travel between two adjacent regions of the jungle, and adjacency is defined to be those regions immediately above/below or to the left/right of another map region. $$$S$$$ is the number of hours that you are able to survive after replenishing your supply of drinking water.

The next line of input contains another two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 500$$$) which denote the number of rows and columns respectively in the jungle grid map. $$$N$$$ lines follow, each containing $$$M$$$ characters that represent regions of space in the jungle. A # character represents an untraversable region, packed with thick brush and trees. A . character represents a traversable region, clear enough to be crossed. A $ character represents a traversable region that also contains drinking water to fully replenish your supply. Lastly, an @ represents your single starting location on the map, and an E character represents the single helicopter pick-up zone which is your exit point from the jungle.

Note, you are guaranteed that there will be fewer than $$$10^3$$$ regions containing drinking water (denoted $).

Print out the minimum number of hours required for you to successfully reach the helicopter pick-up zone and escape! If it is not possible for you to escape the jungle from your start location, output IMPOSSIBLE.

5 21
6 20
#$###.$.###...$.####
#.@..$...##.#.#..###
#.#.####....$.##$###
#.#.#....$#.##....E#
#$..$...###.##.#####
#####..$###.$..##...

150

1 5
5 15
##$....##...#.#
#..#.#.$.##.#.#
#.##$.##...$...
@...##...$#.##E
###...$####.###

IMPOSSIBLE