Светофоры
Светофоры
Все знают, что на ночных улицах опасно. Но в данном случае речь идет не о преступниках и маньяках. Когда наступает ночь, и силы зла властвуют безраздельно, там действуют те, с кем не встретишься днем — темные маги, вампиры и прочая нечисть. Их сила велика, и с ними нельзя справиться обычным оружием. Но по следу "ночных охотников" идут те, кто веками сражается с порождениями сумрака и побеждает их, неукоснительно соблюдая при этом Договор, заключенный тысячелетия тому назад между Светлыми и Темными… Имя им — Ночной Дозор. Их предназначение — сохранение равновесия между Добром и Злом, нарушение которого вызывает разрушения, войны, революции, вселенские катастрофы. Каждый плохой человеческий поступок — измена, предательство, убийство, равно, как и хороший, ложится на чашу весов, перевешивая их то в одну, то в другую сторону. Именно поэтому и силы Света, и силы Тьмы вынуждены существовать в двух мирах: реальном и потустороннем, пытаясь либо подтолкнуть человека к греху, либо отвратить от него…
В городе Н-ске, на одном из перекрестков силы Зла нарушили вековой договор. С другого перекрестка машина "Горсвет" направляется к злополучному месту. За какое время доедут силы Света, если у них есть карта города со схемой работы светофоров, и они поедут по оптимальному маршруту с максимально разрешенной скоростью 60 км/час?
Карта города представляет собой прямоугольник размером N
x M
км (1 ≤ N
, M ≤ 25
). Движение в Н-ске организовано по M
+ 1 улицам, идущим параллельно с севера на юг, и N
+1 авеню, идущим параллельно с запада на восток. Расстояние между двумя соседними улицами (авеню) составляет 250 метров.
По традиции, улицы нумеруются (с запада на восток) подряд идущими натуральными числами, начиная c единицы. Авеню обозначаются (с севера на юг) подряд идущими буквами латинского алфавита, начиная с A
. Таким образом, каждый перекресток города можно однозначно обозначить парой из буквы и числа, например C17.
На каждом перекрестке может находиться светофор. Для i
-го светофора известно число K[i]
(целое 1 ≤ K[i] ≤ 180
), определяющее интервалы цикла смены его состояний: для потоков, едущих с запада и с востока, сначала (K[i]
- 1) секунд горит зеленый свет, затем 1 секунду горит желтый, затем K[i]
секунд горит красный; а для потоков, едущих с севера и с юга, сначала K[i]
секунд горит красный, затем (K[i]
- 1) секунд — зеленый, затем 1 секунду — желтый. Через перекресток разрешается проезжать напрямую или поворачивать на зеленый и желтый свет. В момент поступления сигнала о нарушении договора, каждый светофор находился в D[i]
секундах от начала цикла (D[i]
— целое, 0 ≤ D[i] < 2*K[i]
).
Входные данные
В первой строке входного файла через пробел записаны числа N
и M
. Во второй строке через пробел записаны обозначения начального и конечного перекрестка. В третьей строке записано количество светофоров K
, где 0 ≤ K ≤ (N+1)*(M+1)
. В последующих K
строках через пробел записаны обозначение перекрестка и числа K[i]
и D[i]
.
Выходные данные
Выходной файл должен содержать одно целое число — минимальное время проезда в секундах.
Пример
5 1 F2 A2 3 A2 60 0 C1 100 10 C2 180 180
75