Задача J. Светофоры ≡

Условие

Все знают, что на ночных улицах опасно. Но в данном случае речь идет не о преступниках и маньяках. Когда наступает ночь, и силы зла властвуют безраздельно, там действуют те, с кем не встретишься днем - темные маги, вампиры и прочая нечисть. Их сила велика, и с ними нельзя справиться обычным оружием. Но по следу "ночных охотников" идут те, кто веками сражается с порождениями сумрака и побеждает их, неукоснительно соблюдая при этом Договор, заключенный тысячелетия тому назад между Светлыми и Темными: Имя им - Ночной Дозор. Их предназначение - сохранение равновесия между Добром и Злом, нарушение которого вызывает разрушения, войны, революции, вселенские катастрофы. Каждый плохой человеческий поступок - измена, предательство, убийство, равно, как и хороший, ложится на чашу весов, перевешивая их то в одну, то в другую сторону. Именно поэтому и силы Света, и силы Тьмы вынуждены существовать в двух мирах: реальном и потустороннем, пытаясь либо подтолкнуть человека к греху, либо отвратить от него:

В городе Н-ске, на одном из перекрестков силы Зла нарушили вековой договор. С другого перекрестка машина "Горсвет" направляется к злополучному месту. За какое время доедут силы Света, если у них есть карта города со схемой работы светофоров, и они поедут по оптимальному маршруту с максимально разрешенной скоростью 60 км/час?

Карта города представляет собой прямоугольник размером N x M км. Движение в Н-ске организовано по M+1 улицам, идущим параллельно с севера на юг, и N+1 авеню, идущим параллельно с запада на восток. Расстояние между двумя соседними улицами (авеню) составляет 250 метров.

По традиции, улицы нумеруются (с запада на восток) подряд идущими натуральными числами, начиная c единицы. Авеню обозначаются (с севера на юг) подряд идущими буквами латинского алфавита, начиная с A. Таким образом, каждый перекресток города можно однозначно обозначить парой из буквы и числа, например C17.

На каждом перекрестке может находиться светофор. Для i-го светофора известно целое число K_i, определяющее интервалы цикла смены его состояний: для потоков, едущих с запада и с востока, сначала (K_i - 1) секунд горит зеленый свет, затем 1 секунду горит желтый, затем Ki секунд горит красный; а для потоков, едущих с севера и с юга, сначала K_i секунд горит красный, затем (K_i - 1) секунд - зеленый, затем 1 секунду - желтый. Через перекресток разрешается проезжать напрямую или поворачивать на зеленый и желтый свет. В момент поступления сигнала о нарушении договора, каждый светофор находился в D_i секундах от начала цикла.

Формат входного файла

В первой строке входного файла через пробел записаны числа N и M. Во второй строке через пробел записаны обозначения начального и конечного перекрестка. В третьей строке записано количество светофоров K. В последующих K строках через пробел записаны обозначение перекрестка и числа K_i и D_i.

Формат выходного файла

Ограничения

Примеры тестов

5 1
F2 A2
3
A2 60 0
C1 100 10
C2 180 180

75

5 5
A1 F6
7
A3 120 0
B3 180 0
C3 180 60
D3 100 60
E3 100 0
F1 5 0
F2 3 0

150