C. Древний замок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кэл Кестис обнаружил древний храм Силы. Вход в храм находится в прямоугольной пещере. Чтобы попасть в храм, нужно открыть рунический замок, которым запечатан вход.

Пещера, в которой находится вход в храм, имеет размеры $$$n \times m$$$ метров, и поделена на квадраты размера $$$1 \times 1$$$ метр. Представим пещеру в виде таблицы $$$n \times m$$$, строки которой пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$m$$$ слева направо. В некоторых квадратах находятся рунические камни, а остальные квадраты свободны. Кэл может перемещаться только по свободным квадратам. За единицу времени он может переместиться из квадрата в соседний по стороне.

Сейчас Кэл находится в некотором квадрате пещеры. Чтобы открыть вход в храм, нужно в правильном порядке коснуться нескольких рунических камней. После чего, Кэл должен дойти до квадрата, в котором откроется вход в храм. Чтобы коснуться рунического камня, расположенного в некотором квадрате, Кэл должен встать в квадрате, соседнем по стороне. На то, чтобы коснуться камня, Кэл не тратит дополнительного времени.

За Кэлом гонятся инквизиторы Империи, и он хочет узнать, за какое минимальное время можно открыть замок и войти в храм. Помогите ему узнать эту величину.

Входные данные

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — размеры пещеры и длина последовательности камней, до которых Кэл должен дотронуться ($$$1 \le n, m \le 100$$$; $$$0 \le k \le 100$$$).

В следующих $$$n$$$ строках дано по $$$m$$$ символов — описание пещеры. Символ «#» соответствует непроходимой клетке, содержащей камень. Все остальные клетки свободны. Символ «S» соответствует квадрату, в котором Кэл находится изначально. А символ «F» соответствует квадрату, в котором откроется вход в храм. Кэл должен будет прийти в него после того, как откроет замок. Все остальные символы равны «.». Гарантируется, что символы «S» и «F» встречаются ровно по одному разу.

В следующих $$$k$$$ строках даны по два целых числа $$$x_i$$$ и $$$y_i$$$ — номер строки и столбца, на пересечении которых находится $$$i$$$-й камень, которого Кэл должен коснуться. Гарантируется, что квадрат на пересечении строки номер $$$x_i$$$ и столбца номер $$$y_i$$$ содержит камень для всех $$$i$$$ от $$$1$$$ до $$$k$$$.

Выходные данные

Если Кэл не сможет открыть замок и войти в храм, выведите число $$$-1$$$. Иначе, выведите минимальное время, необходимое, чтобы открыть замок и дойти до входа в храм.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
111$$$k = 0$$$первая ошибка
234$$$k \le 5$$$1первая ошибка
3551, 2первая ошибка
Примеры
Входные данные
3 5 3
#....
####.
FS...
1 1
2 3
2 2
Выходные данные
17
Входные данные
3 5 1
#....
#####
FS...
1 1
Выходные данные
-1
Входные данные
3 5 0
F#...
.#.#.
...#S
Выходные данные
10
Примечание

В первом примере, Кэл сначала должен дойти до квадрата $$$(1, 2)$$$ за $$$8$$$ шагов. Коснуться камня $$$(1, 1)$$$. Перейти в соседний справа квадрат. Коснуться камня $$$(2, 3)$$$. Затем, дойти до квадрата $$$(3, 2)$$$ за $$$7$$$ шагов. Коснуться камня $$$(2, 2)$$$. Перейти в соседний слева квадрат. После чего, его маршрут закончится. Суммарно он потратит $$$8 + 1 + 7 + 1 = 17$$$ единиц времени.