eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Светофоры

Светофоры

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

В городе Н-ске, на одном из перекрестков силы Зла нарушили вековой договор. С другого перекрестка машина "Горсвет" направляется к злополучному месту. За какое время доедут силы Света, если у них есть карта города со схемой работы светофоров, и они поедут по оптимальному маршруту с максимально разрешенной скоростью 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].

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

Выходной файл должен содержать одно целое число — минимальное время проезда в секундах.

Пример

Входные данные #1
5 1
F2 A2
3
A2 60 0
C1 100 10
C2 180 180
Выходные данные #1
75