Задача 1. Стритрейсинг

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

 

Ты стоишь на светофоре на своей машине, а рядом с тобой или через машину стоит такой же, как ты. Ты с ним не знаком, ты даже понятия не имеешь, кто он такой, но ты знаешь: сейчас начнется оно... Вы не сигналите друг другу, не газуете, но оба понимаете: да, сейчас будет оно, то самое. И по сигналу светофора с визгом резины и ревом выхлопной системы вы срываетесь вперед, пытаясь выяснить, чья машина быстрее. Из всех машин, стоящих на светофоре, только вы вдвоем сорвались. Если одним из них был ты, то ты настоящий стритрейсер.

Чаще всего сибирские гонщики собираются на недостроенной взлетно-посадочной полосе за городом. Ориентир - развилка перед аэропортом Толмачёво, после которой поворачиваете налево и едете минут пять. Потом поворот направо на запасную полосу - и вы на месте. Соревнуются и днем и ночью.

Однажды ночью сотрудники ГИБДД расставили вдоль трассы знаки ограничения скорости и уселись в засаде с радаром. Очередные соревнования пришлось проводить, соблюдая скоростной режим. Напоминаем, что знак ограничения скорости предписывает двигаться со скоростью, не превышающей указанную на нем. Действие знака начинается в месте установки и прерывается следующим знаком. С начала трассы до первого знака действует обычное ограничение 90 км/час.

За какое минимально возможное время проедет трассу ваша машина, если максимальное ускорение, развиваемое двигателем a₁ м/сек², а максимальное замедление торможения a₂ м/сек²? В начале трассы ваш автомобиль неподвижен.

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

В первой строке файла записано вещественное число S - длина трассы (0 < S £ 10000 м).

Вторая строке входного файла содержит два вещественных числа a₁ и a₂ (0 < a₁, a₂ £ 10 м/сек²). В третьей строке находится целое  число N - количество установленных знаков (0 £ N £ 100). В последующих N строках файла даны через пробел пары вещественных чисел S_i, V_i - расстояние от начала трассы, на котором установлен i-ый знак (1 £ i £ N)  и ограничение скорости в км/час, указанное на нём (0 £ S_i < S, 0 < V_i £ 500), соответственно. Знаки записаны по порядку, по мере удаления от старта (S_i < S_i+1 при 1 £ i < N).

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

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

Примеры

Входной файл: input.txt	Выходной файл: output.txt
1000 5 10 0	42.50
1000 5 10 1 100 45	78.81

Задача 2. Прогрессии

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	2 секунды на тест
Ограничение по памяти:	16 Мб

 

Жители страны Прогрессляндии слишком буквально поняли лозунг своего великого правителя "Больше прогрессий - хороших и разных" и решили сосчитать, сколько всего прогрессий они могут придумать. К нашему великому счастью, они знают только целочисленные строго возрастающие арифметические прогрессии в диапазоне от 0 до N, причем прогрессия обязательно должна начинаться со священного числа 0 и иметь хотя бы два элемента.

К сожалению, они недостаточно прогрессивны, чтобы решить эту проблему. Помогите им.

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

В первой строке  входного файла записано одно число  N  (0 £ N £ 10¹²).

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

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

Пример

Входной файл: input.txt	Выходной файл: output.txt
3	5

 

Задача 3. Кин-дза-дза Reload

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	10 секунд на тест
Ограничение по памяти:	16 Мб

Краткий пацакско-чатланский толковый словарь

КЦ           - спичка

ЦАК          - колокольчик для носа

ЭЦИХ         - ящик для узников

ЭЦИЛОПП      - представитель власти

ПЕПЕЛАЦ      - межзвёздный корабль

ГРАВИЦАППА   - деталь от мотора пепелаца

КЮ           - допустимое в обществе ругательство

КУ           - все остальные слова

После наступления в России эпохи капитализма с нечеловеческим лицом, два постаревших космонавта (Гедеван Александрович и Владимир Николаевич), потеряв все свои льготы и привилегии, отправились на планету Плюк (215-ая в тентуре, спирали Кин-дза-дза) в поисках достойной жизни. Они планировали организовать несколько юбилейных сольных концертов, а на заработанные деньги открыть бар "Последний выдох".

Однако, прилетев на Плюк, наши герои увидели, что там не лучше, чем в России. Оказалось, что за время их отсутствия властитель планеты господин ПэЖэ и прочие эцилоппы установили абсолютный контроль над личной жизнью жителей планеты - пацаков при помощи глобальной системы слежения "Эцих-сат", и теперь вволю не попоёшь, да и вообще передвигаться надо вприсядку и, звеня цаком. Воистину настало время для революционной деятельности! Для этого нашим героям очень нужно найти место на планете, которое не подвергается слежению Эцих-сатом, и организовать там партийную ячейку.

После долгих мытарств, за немыслимые деньги (1 коробок КЦ) старый друг Уэф выкупил секретную информацию об Эцих-сате. Эта система состоит из неподвижных пепелацев, находящихся на стационарных орбитах Плюка. С каждого из пепелацев зоркий чатланин следит за той частью планеты, которая находится в области его прямой видимости (при этом линию своего горизонта он не прослеживает).

Из старого издания школьного атласа было извлечено, что география на планете вполне аналогична земной, за исключением того, что Плюк - шар радиуса 1000 км. У него есть несколько стационарных орбит, не обязательно лежащих в плоскости экватора. Самая низкая плюкстационарная орбита имеет высоту 500 метров, а самая дальняя от поверхности - 100000 км.

Теперь, зная все необходимое, вам нужно найти точку на Плюке, которая не наблюдается ни одним пепелацем или определить, что такой точки нет.

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

В первой строке входного файла указано 1 £ N < 1000 - количество пепелацев в системе.

В следующих N строках через пробелы указаны: высота орбиты пепелаца в километрах, широта и долгота (в виде десятичной дроби). Эти три числа задаются с точностью до третьего знака после запятой. Широта меняется в пределах от -90.0 (южный полюс) до 90.0 (северный полюс). Долгота меняется в пределах от -180 градусов (западная долгота) до +180 градусов (восточная долгота).

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

В выходной файл в одну строку, через пробел, надо вывести широту и долготу любой точки на планете, где нет наблюдения. Числа должны быть выведены в формате, аналогичном формату ввода, но с точностью до восьмого знака после запятой. Если же такой точки на планете не осталось, то в файл надо вывести одну строку:

Chatlane pacakam na golovu seli! Kyu!

Пример

Входной файл: input.txt	Выходной файл: output.txt
4 10000 90 0 10000 -90 0 5000 0 30 5000 0 -150	0 120

Задача 4. Памятник

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

 

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

Памятник имеет вид параллелепипеда. Он очень тяжелый, его нельзя передвигать, можно только переворачивать через ребра. На всех боковых сторонах памятника находится одно и то же изображение.

Главная площадь города имеет форму прямоугольника со сторонами N и M (1 £ M £ N £ 100). С одним из углов площади совмещено начало координат. Ось OX проходит по большей стороне, а OY - по меньшей. Площадка, на которую нужно поставить памятник, точно совпадает по размерам с основанием памятника. Это прямоугольник со сторонами A и B (1 £ А £ N, 1 £ B £ M, B £ A), которые параллельны сторонам площади (большая сторона площадки параллельна большей стороне площади). Расположение площадки задается  координатами ее угла, ближайшего к началу координат.

Определим длину элементарного переворота памятника как длину ребра, перпендикулярного ребрам основания, на котором памятник находился до этого переворота. Длина траектории перемещения памятника определяется как сумма длин элементарных переворотов. Требуется найти наименьшую длину траектории, по которой можно переместить памятник и поставить правильно.

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

В первой строке входного файла записаны два числа N и M - размеры площади.

В следующей строке заданы размеры памятника и координаты площадки. Это пять чисел A, B, C, X, Y, где. А и B - длины ребер основания памятника,  C - его высота (1 £ C £ 100),  X и Y - координаты (0 £ X £ N - A, 0 £ Y £ M - B). Все числа целые и записаны через пробел.

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

В выходной файл необходимо вывести одно целое число - длину минимальной траектории перемещения памятника. Если памятник переместить невозможно, то нужно вывести 0.

Пример

Входной файл: input.txt	Выходной файл: output.txt
10 10 1 1 1 2 2	6

Задача 5. Мешок фальшивых денег

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

 

Имеется N мешков монет, пронумерованных от 1 до N. На каждом мешке написано число лежащих в нем монет. Один мешок наполнен только фальшивыми монетами. В остальных мешках все монеты - настоящие.

Настоящая монета весит 10 граммов, фальшивая - 9 граммов.

Имеются весы, которые показывают общий вес положенных на них монет.

Требуется определить наименьшее число взвешиваний, которые потребуются, для того чтобы установить,  в каком мешке фальшивые монеты, при абсолютном невезении.

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

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

В первой строке  входного файла записано одно число  N - количество мешков (1 £ N £ 30000).

Начиная со следующей строки, записано N чисел, обозначающих число монет в соответствующем мешке.  Эти числа находятся в диапазоне от 1 до 100000.

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

В выходной файл нужно вывести одно число - минимальное количество взвешиваний.

Пример

Входной файл: input.txt	Выходной файл: output.txt
3 5 10 2	1

      

 

Задача 6. Молекулы

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

Органические вещества отличаются потрясающим разнообразием. Они различаются по  химическому составу (по пропорциям составляющих вещество элементов), по химической формуле молекул (по порядку расположения и химическим связям атомов) и по пространственной форме молекул. Проблема восстановления  по химическому составу органического вещества его химической формулы и проблема пространственного конфигурирования молекул по их химическим формулам - чрезвычайно актуальные задачи биоинформатики. К сожалению, они отличаются высокой вычислительной сложностью.

Рассмотрим проблему химической формулы и пространственной конфигурации органических молекул при следующих упрощающих предположениях:

1.      вещество состоит только из атомов водорода H (валентность 1), кислорода O (валентность 2), азота  N (валентность 3) и углерода C (валентность 4);

2.      молекула или группа молекул вещества представляет собой плоскую прямоугольную решётку из m строк и n столбцов, в узлах которой могут находиться или атомы перечисленных элементов, или <дырки> - пустоты, не занятые никаким  атомом;

3.      каждый атом в решётке может быть связан с атомами, своими соседями по решётке, но с каждым соседом он связан не более чем одной связью, а общее число его связей совпадает с его валентностью.

Ваша задача - написать программу, которая для данной прямоугольной решётки, в узлах которой могут находиться элементы H, O, N, C или дырки <.>, определит, может ли она описывать структуру одной или нескольких молекул.

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

Входной файл для программы описывает одну решетку. В его первую строку  записаны через пробел два целых чисел M и N (1 £ M, N £ 50), задающих число строк и число столбцов этой решётки. Следующие M строк содержат ровно по N символов `H`, `O`, `N`, `C`, `.`, представляющих элементы или <дырки> в порядке слева направо в соответствующей строке решётки.

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

В выходной файл программы нужно вывести слово Valid, если данная решетка может описывать структуру одной или нескольких молекул, или Invalid, в противном случае.

Примеры

Входной файл: input.txt	Выходной файл: output.txt
3 4 HOH. NCOH OO..	Valid
3 4 HOH. NCOH OONH	Invalid
2 3 HOH HOH	Valid
4 10 OOOOOOOOOO OOOOOOOOOO OOOONOOOOO OOOOOOOOOO	Invalid

Задача 7. Перекачка данных

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	4 секунды на тест
Ограничение по памяти:	16 Мб

 

Имеется два компьютера, с одного из которых нужно передать информацию размером V мегабайт на другой. В качестве носителя информации имеется два USB-диска с размерами V₁ и V₂ мегабайт, скоростями чтения R₁ и R₂ и записи W₁, W₂ мегабайт в секунду, соответственно.

Конструктивные особенности дисков таковы, что чтение или запись происходят целое число секунд, в том числе, если на источнике информации или на приемнике места меньше, чем может быть записано за секунду, копирование будет все равно занимать секунду. На каждом из компьютеров имеется только один USB-разъем. Поэтому в один и тот же момент времени можно либо переписывать информацию с компьютера на один носитель, либо читать данные с диска и переписывать их на компьютер. Требуется  определить, за какое минимальное время можно перенести данные с одного компьютера на другой, если переключение дисков происходит за нулевое время.

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

В первой строке входного файла записано одно целое число V - объем информации, который нужно перекачать.

В следующих двух строках записано по три числа  - параметры каждого из дисков. Сначала V₁, R₁, W₁, а затем, соответственно, V₂, R₂ и W₂.

Все числа даны в диапазоне от 1 до 300, включительно.

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

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

Пример

Входной файл: input.txt	Выходной файл: output.txt
80 10 10 10 20 20 20	6

 

Задача 8. Синтаксис UML

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

UML (Unified Modelling Language) - унифицированный язык моделирования, который применяется для разработки сложных объектно-ориентированных программных проектов. Одним из элементов UML является диаграмма деятельности, предназначенная для описания алгоритмов поведения взаимодействующих параллельных процессов.

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

Назовем схему правильной, если она состоит из вершин следующих пяти видов:

1.      Состояние. В такой вершине выполняется некоторое действие. Она имеет не более одной входящей дуги и не более одной выходящей.

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

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

4.      Разделение. Такая вершина имеет одну входящую дугу и не менее двух выходящих. Она предназначена для описания параллельного поведения системы. При исполнении разделения управление передается по всем выходящим дугам.

5.      Соединение. Эта вершина имеет две или более входящих дуг и одну выходящую. Соединение исполняется, если  оно получает управление по всем входящим дугам.

Таким образом, условное поведение изображается с помощью ветвлений и слияний, а параллельное поведение - с помощью разделений и соединений. В  UML-схеме выделены две вершины вида состояние: начальная и конечная. Функционирование диаграммы начинается в начальном состоянии и заканчивается в конечном. Каждая вершина достижима из начального состояния и из каждой вершины достижимо конечное состояние. Путь - это последовательность вершин в диаграмме. Входом вершины назовем такую вершину, у которой выходящая дуга входит в данную вершину. Выходом вершины назовем такую вершину, у которой входящая дуга выходит из данной вершины.

Некоторые сочетания ветвлений и разделений сложно или даже невозможно интерпретировать на традиционных фон-неймановских вычислительных системах. Одной из причин является то, что они порождают потенциально бесконечное количество параллельных путей. Поэтому и стандарт UML, и большинство его реализаций определяют различные ограничения на структуру диаграммы.

Ваша задача - написать программу, которая просматривает описание диаграммы и проверяет ее правильность и соответствие следующим ограничениям:

*         Пути исполнения, вышедшие из разделения, не могут проходить через одно и то же состояние, ветвление или слияние.

*         Пути исполнения, вышедшие из одного ветвления, не могут проходить через одно и то же состояние, разделение или соединение.

*         Каждому ветвлению соответствует отдельное слияние, в котором заканчиваются всевозможные пути исполнения, начавшиеся в этом ветвлении.

*         Каждому разделению соответствует одно соединение, в котором заканчиваются все пути исполнения, начавшиеся в этом разделении.

*         Входы и выходы вершин вида ветвление, разделение, слияние и соединение могут быть только состояниями.

*         Входы и выходы состояний могут быть любыми вершинами.

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

*         Аналогично, для нескольких ветвлений можно указывать одно общее слияние.

 

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

S - состояние (State),

D - ветвление (Decision Activity),

M - слияние (Merge),

B - разделение (Synchronization Bar),

J - соединение (Join).

Пример простой диаграммы деятельности языка UML приведен на рисунке. В нем 0 - началь-ное состояние,  17 - заключительное, 2, 10 - разделение, 14 - соединение, 5 - ветвление, 8 - слияние. Все остальные вершины диаграммы - состояния.

 

 

 

 

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

В первой строке входного файла указано целое число N (N £ 10000) - количество элементов диаграммы. Вершины диаграммы пронумерованы числами от 0 до N - 1. Начальное состояние имеет номер 0,  а заключительное - (N - 1). В каждой из следующих N строк описываются по порядку вершины диаграммы, по одной на строке. Описание одной вершины содержит в первой позиции строки один символ - вид  вершины, а далее (в зависимости от вида вершины) может следовать информация о входах и выходах. Для начального состояния указан только номер выхода, а для заключительного - только номер входа. Для всех состояний, кроме начального и заключительного, указан сначала номер входа,  и затем номер выхода. Для остальных видов вершин дополнительная информация отсутствует.

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

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

 

Примеры

Входной файл: input.txt	Выходной файл: output.txt
18 S 1 S 0 2 B S 2 9 S 2 5 D S 5 8 S 5 8 M S 3 10 B S 10 14 S 10 14 S 10 14 J S 14 17 S 8 14 S 15	CORRECT
7 S 1 M S 1 3 B S 3 1 S 3 6 S 5	INCORRECT

Задача 9. Города - конкуренты

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	5 секунд на тест
Ограничение по памяти:	16 Мб

 

В стране Флатландии имеется N городов, каждый город выпускает один определенный товар из M товаров. Города, выпускающие один и тот же товар, являются городами-конкурентами. Города Флатландии хотят объединиться в торговую сеть. Как показали исследования,  для того, чтобы какие-то города могли объединиться в торговую сеть, необходимо и достаточно, чтобы из любого города A можно было добраться по дорогам сети в любой другой город B. Причем, в такой сети не должно быть дорог между городами-конкурентами, т.е. города-конкуренты не являются соседями в этой сети.

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

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

В первой строке входного файла записаны через пробел два целых числа N и M (1 ≤ N ≤ 200, 1 ≤ M ≤ 200). В последующих N строках описаны города Флатландии, описание каждого города занимает одну строку. В соответствующей строке записаны через пробел три целых числа X_i, Y_i, Z_i, где  X_i и Y_i - координаты i-го города, a Z_i - номер продукции, которую выпускает этот город (-10000 £ X_i , Y_i £.10000, 1 £ Z_i £ M, 1£ i £ N).

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

  В первую строку выходного файла необходимо вывести одно вещественное число с точностью до 0.001 - минимальную длину сети дорог.

Если города объединить в торговую сеть невозможно, то вывести -1.

Примеры

Входной файл: input.txt	Выходной файл: output.txt
8 3 3 3 1 3 10 1 5 6 2 10 6 3 10 10 2 15 3 1 15 6 3 15 10 2	29.909
4 1 0 0 1 0 5 1 5 0 1 5 5 1	-1

 

 

 

 

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

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	3 секунды на тест
Ограничение по памяти:	16 Мб

 

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

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

Карта города представляет собой прямоугольник размером N´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.

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

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

Примеры

Входной файл: input.txt	Выходной файл: output.txt
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