21717번 - Кенгуренок Лео 다국어

Заколдованный магом кенгуренок Лео очнулся в тесном Каньоне. Перед его глазами предстала неприступная стена, поблизости ---  грозные остатки выветренных тысячелетиями скал. Он быстро понял, что злые силы лишили его возможности шагать или поворачиваться. <<Да, но я могу совершать прыжки вбок!>> --- гениальная идея  посетила его животный, но очень сообразительный мозг. И мужественный Лео, превозмогая страх и боль, решил спастись --- его миссия была крайне важна для всего Мира. Он должен добраться до края Каньона, передвигаясь только влево и вправо прыжками через и на каменные столбы, жалко напоминающие очертания некогда великих и нерушимых скал.

Но Лео знал свои возможности --- он всего лишь кенгуру. А обыкновенные кенгуру не умеют мыслить логически и планировать свои действия. Обыкновенные кенгуру$\ldots$ Уже отчаявшись и впав в полную апатию, он нашел просвет в железном занавесе, отделяющем его от столь желанного выполнения Великой Миссии. Он вспомнил о людях$\ldots$

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

Это послание попало к Вам в руки. Спасите кенгуру!

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

Внутри Каньона Лео может перемещаться только прыжками. Траектория прыжка заколдованного Лео состоит из трех отрезков: вертикального подъема из точки его расположения на высоту $p$, горизонтального перемещения на $q$ единиц влево или вправо и последовательного вертикального спуска из этой точки не более, чем на $r$ единиц. Числа $p$, $q$ и $r$ --- натуральные, причем сумма $p$ и $q$ равна заданной величине $n$. Ни один из отрезков траектории прыжка Лео не может пересекать границы столбов внутри каньона или касаться их. Следующий прыжок начинается в точке приземления. Для того, чтобы выбраться из Каньона, Лео достаточно попасть в точку левее или правее его краев.

Первая строка входного файла содержит шесть разделенных пробелами целых чисел в следующем порядке: $-10\,000 \le A \le 0,\ 0 < B \le 10\,000$ --- координаты левого и правого краев Каньона, $0 \le H \le 1\,000$ ---  их высота, $2 \le n \le 1\,000$ --- сумма длин двух первых отрезков траектории, $0 < r \le 1\,000$ --- верхняя граница величины третьего отрезка, а также $0\le m<20\,000$ --- количество столбов внутри Каньона.

В последующих $m$ строках находятся целые числа $-10\,000 \le X_i < Y_i \le 10\,000$ --- координаты краев $i$-ого столба и  $0 \le Z_i \le 1\,000$ --- его высота.  Никакие два столба не пересекаются, но могут касаться друг друга  и краев каньона. Изначально кенгуру находится вне всех столбов, в точке каньона с координатой $0.5$ и высотой 0.

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

Кенгуру делает 4 прыжка, каждый вверх на 2 и вправо на 1.