Світлофори
Усі знають, що на нічних вулицях небезпечно. Але в даному випадку мова йде не про злочинців та маньяків. Коли настає ніч, і сили зла володарюють неподільно, там діють ті, з ким не зустрінешся вдень — темні маги, вампіри та інша нечисть. Їх сила велика, і з ними не можна боротись звичайною зброєю. Але по сліду "нічних мисливців" йдуть ті, хто віками бореться з породженнями пітьми і перемагає їх, недоторканно дотримуючись при цьому Договір, заключений тысячоліття тому назад між Світлими і Темними… Ім'я їм — Нічна Варта. Їх призначення — збереження рівноваги між Добром і Злом, порушенння якої викликає руйнування, війни, революції, всесвітні катастрофи. Кажен не гідний людський поступок — зрада, підлість, вбивство, так само, як і гарний, кладуться на терези ваг, переважаючи їх то в одну, то в іншу сторону. Саме тому і сили Світла, и силы Пітьми змушені існувати в двох світах: реальному та потойбічному, намагаючись або підштовхнути людину до гріха, або відвернути від нього…
В місті Н-ську, на одному з перехресть сили Зла порушили віковий договір. З іншого перехрестя автомобіль "Місксвітло" направляється до злощасного місця. За який час доїдуть сили Світла, якщо у них є карта міста зі схемою роботи світлофорів, і вони поїдуть по оптимальному маршруту з максимально дозволеною швидкістю 60 км/год?
Карта міста являє собою прямокутник розміром N x M км (1 ≤ N, M ≤ 25). Рух в Н-ську організовано по M+1 вулицям, що йдуть паралельно з півночі на південь, та N + 1 авеню, що йдуть паралельно із заходу на схід. Відстань між двома сусідніми вулицями (авеню) складає 250 метрів.
По традиції, вулиці нумеруються (с заходу на схід) підряд йдучими натуральними числами, починаючи з одиниці. Авеню позначаються (з півночі на південь) підряд йдучими літерами латинського алфавіту, починаючи з 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.
Вихідні дані
Вихідний файл повинен містити одне ціле число — мінімальний час проїзду в секундах.