16. Побег
Остап Бендер убегает от разъяренной мадам Грицацуевой через длинный коридор, разделенный сложной системой лифтов, располагающихся последовательно один за другим и беспрерывно ездящих вверх-вниз. Оба конца коридора расположены на одном уровне. При этом и товарищ Бендер, и вдова могут входить в лифт, выходить из него, а также пересаживаться с лифта на лифт при условии, что лифты находятся на одинаковой высоте друг с другом или с коридором. Добежав до конца коридора, он запирает спасительную дверь. После этого бриллиантовой вдовушке остается только лишь поудобней устраиваться на ночлег.
Наша цель — помочь Остапу найти минимальную скорость, достаточную для того, чтобы брошенная вдова не смогла его догнать.
Входные данные
В первой строке входного файла приведено пять положительных целых чисел t, v, a, N, b: t — время старта вдовы (Остап стартует в нулевой момент времени), v — скорость мадам Грицацуевой, a — длина первоначального отрезка коридора до первого лифта, N — количество лифтов, b — длина последнего участка коридора (расстояние от последнего лифта до спасительной двери). Все эти числа не превосходят 1000.
В следующих N строках приводится описание каждого из N лифтов — по шесть целых чисел в строке. Описание i-го лифта задается числами Vi, Ti, Hi, T0i, Wi и Zi.
Vi – скорость вертикального перемещения лифта, она постоянна, меняется только ее направление — вверх или вниз (1 <= Vi <= 1000).
Ti – полупериод поездки лифта — время, которое он будет ехать вверх или вниз (1<= Ti <= 1000).
Hi – первоначальная высота положения лифта, отсчитываемая от уровня коридора, который принимается за 0 (?1000 <= Hi <= 1000).
T0i – время, отсчитываемое от начального момента времени до первой смены направления (1 <= T0i <= Ti).
Wi — длина платформы лифта (расстояние, которое необходимо преодолеть, чтобы пересесть на следующий лифт, 1 <= Wi <= 1000).
Zi принимает одно из двух значений — либо 1, либо -1. Оно показывает первоначальное направление движения лифта — вверх или вниз соответственно.
Выходные данные
В выходной файл необходимо вывести одно вещественное число, округленное до трех знаков после запятой, минимальную скорость, достаточную для того, чтобы убежать от мадам Грицацуевой. Гарантируется, что эта скорость не превосходит 10^6. Если Остапу убежать никак не удастся, нужно вывести -1.
Примеры
input.txt
2 1 2 1 3 2 2 2 1 4 1
output.txt
1
input.txt
1 1 2 1 3 2 2 2 1 4 1
output.txt
-1
Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru
| 