F1. Скейгербосс
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Ктулху решил поймать Скейгербосса. Скейгербосс узнал об этом и решил спрятаться в стае своих скейгеров. Каждый скейгер за исключением Скейгербосса является мужской или женской особью. Пол Скейгербосса — "другой".

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

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

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

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

Первая строчка содержит 4 целых числа: n, m, males, females (0 ≤ males, females ≤ n·m). n и m — размеры карты, males и females — количества мужских особей и женских особей соответственно.

Следующие n строк содержат карту. Каждая строка содержит m символов. Символ '.' обозначает свободную клетку, символ '#' обозначают клетку с препятствием.

Следующая строка содержит 3 целых числа r, c и t (1 ≤ r ≤ n, 1 ≤ c ≤ m, 1 ≤ t ≤ 109): текущие координаты Скейгербосса и время, требуемое Скейрбоссом для того, чтобы переместиться в соседнюю клетку. Следующие males строк содержат координаты и времена мужских особей в таком же формате как и для Скейгербосса. Следующие females строк содержат координаты и времена женских особей в таком же формате как и для Скейгербосса. (Для всех координат и времен выполняются те же самые ограничения, что и для координат и времени Скейгербосса.) Все скейгеры находятся в клетках без препятствий.

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

  • В подзадаче F1 (14 баллов) выполняется 1 ≤ n, m ≤ 11.
  • В подзадаче F2 (6 баллов) выполняется 1 ≤ n, m ≤ 22.
Выходные данные

Выведите минимально возможное время, требуемое для того, чтобы все скейгеры выглядели милыми ботанами, или -1, если это невозможно.

Примеры
Входные данные
4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2
Выходные данные
2
Входные данные
2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
Выходные данные
-1
Примечание

Рассмотрим первый пример. Скейгеры прячутся на карте размером 4x4. Скейгербосс изначально находится в клетке (2, 1) и может перемещаться из клетки в соседнюю за 1 единицу времени. Кроме него, на карте есть 2 мужских и 3 женских особи. Одна из женских особей находится в клетке (1, 1), а все остальные особи находятся в клетке (2, 1). Все они перемещаются в соседние клетки за 2 единицы времени. Если Скейгербосс и женская особь из клетки (1, 1) перейдут в клетку (1, 2), а одна женская и одна мужская особь из числа оставшихся перейдут в клетку (1, 1), тогда все скейгеры станут выглядеть милыми ботанами, и на это потребуется всего 2 единицы времени.