2067. Скользкий путь

Люк Скайуокер ступил на скользкий путь! К счастью, его не влечет Темная сторона. Он всего лишь оказался на планете Хот, целиком покрытой снегом и льдом, потому передвигаться по местности необходимо крайне осторожно. Люку необходимо добраться из точки A в точку B и доставить ценную и хрупкую посылку.

Для простоты будем считать, что местность разбита на квадраты и представляет из себя прямоугольник размером `n` на `m`. Каждая клетка может быть одного из трех типов: здание, сугроб, либо лед. Перемещаться Люк может только между соседними клетками. Соседними считаются клетки, имеющие общую сторону. Перемещение между любыми двумя клетками занимает ровно одну единицу времени. Каждая клетка имеет свою высоту – целое число.

Между соседними клетками зданий можно перемещаться без каких-либо ограничений. Также из здания можно переместиться в соседний сугроб. Из сугроба можно попасть в соседнее здание. Из сугроба можно перейти либо в соседний сугроб, либо на соседнюю клетку со льдом, если высота новой клетки не больше изначальной. Из клетки со льдом можно переходить в соседнюю клетку со льдом или сугробом, если высота новой клетки не больше изначальной. Если же Люк переходит из клетки со льдом в клетку со льдом, высота которой строго меньше, то он начинает скользить в том же направлении. Люк останавливает скольжение, если следующей клеткой на его пути встречается сугроб, клетка со льдом, высота которой больше высоты той клетки, в которой он находится, либо край карты. В этом случае Люк снова может идти в любом направлении из той клетки, в которой он остановился. Если же Люк встречает на своем пути стену здания, то он оказывается не в силах остановить движение и разбивает посылку.

Люку необходимо как можно скорее доставить это посылку из точки A в точку B. Помогите ему найти кратчайший путь, при котором его груз уцелеет.

В первой строчке входного файла заданы два числа `n` и `m` (`1\ ≤\ n,\ m\ ≤\ 500`) – размеры карты. Во второй строке находятся два числа `a_r`, `a_c` (`1\ ≤\ a_r\ ≤\ n,\ 1\ ≤\ a_c\ ≤\ m`) – номер строки и номер столбца, в которых находится точка A. В третьей строке находятся два числа `b_r`, `b_c` – описание точки B в том же формате. В каждой из следующих `n` строчек находится `m` символов. Если соответствующий символ равен `B`, то в этой клетке находится здание, `S` – сугроб и `I` – лед. В следующих `n` строчках находится описание рельефа местности. В каждой из этих строчек – по `n` целых чисел – высота соответствующей клетки на карте. Высота каждой точки – целое число `h_{{ij}}` (`0\ ≤\ h_{{ij}}\ ≤\ 10^9`).

Гарантируется, что точки A и B находятся в зданиях.

В выходной файл выведите длину кратчайшего пути из A в B, либо Impossible, если пути не существует.

3 5
1 1
3 5
BISSS
SIIIS
SSSIB
10 10 5 5 5
10 10 5 3 1
10 10 5 5 1

6