ЗАДАЧА G
Видеомагнитофон
| Имя входного файла: | vhs.in |
| Имя выходного файла: | vhs.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Ничего себе, вашу маму и там и тут передают, до чего техника дошла!
Из мультфильма «Зима в Простоквашино»
Почтальон Печкин всегда очень любил различные технические устройства. После того, как он получил желанный велосипед, Печкин решил купить себе видеомагнитофон, чтобы записывать сериалы, идущие в одно время по разным каналам. Сказано – сделано, и почтальон приобрел староватый, но надежный видеомагнитофон VHS.
К магнитофону прилагалась одна кассета на L минут. А поскольку в Простоквашино все уже перешли на DVD, еще одну VHS кассету купить не так-то просто. Поэтому Печкин может записывать передачи только на одну кассету, которая шла в комплекте с видеомагнитофоном.
Существенный недостаток всех кассетных видеомагнитофоном состоит в том, что видео записывается последовательно на пленке. Поэтому при записи нужно быть осторожным, чтобы не стереть ранее записанные фрагменты. Такая проблема стоит и перед Печкиным. Он уже записал на кассете N непрерывных фрагментов. Теперь он хочет разместить на кассете новую серию сериала так, чтобы не повредить ни одного из уже записанных фрагментов.
Серия сериала представляет собой непрерывный блок длительностью D1 минут, рекламу длиной R минут и еще один непрерывный блок длиной D2 минут. Изначально кассета перемотана на начало. Почтальон Печкин до начала сериала может перемотать кассету в любое место и начать запись. В течение рекламы почтальон может перематывать кассету в любом направлении, чтобы после рекламы записать второй блок. Видеомагнитофон Печкина перематывает кассету в любую сторону со скоростью в V раз большей, чем скорость записи или воспроизведения.
Почтальон Печкин очень ценит свое время и поэтому хочет, чтобы суммарное время перемотки (до начала сериала и во время рекламы) было минимально возможным. Подскажите почтальону, как следует записывать сериал, или скажите, что это невозможно.
Входные данные
Первая строка входного файла содержит шесть целых чисел: N, L, V, D1, R, D2 (0 <= N <= 1000, 1 <= L, V, D1, R, D2 <= 109). Каждая из следующих N строк описывает один из уже записанных фрагментов и содержит два целых числа Ai и Bi (0 <= Ai < Bi <= L) – метки начала и конца фрагмента. Метка – это число минут от начала кассеты, может быть от 0 до L включительно. Приведенные фрагменты не имеют общих точек и перечислены в произвольном порядке.
Выходные данные
Если записать серию сериала можно, то выведите в выходной файл единственное вещественное число с шестью знаками после запятой – наименьшее суммарное время перемотки кассеты. Если записать серию не получится, то выведите слово “IMPOSSIBLE” (без кавычек).
Пример
| vhs.in | vhs.out |
|---|---|
|
|
|
|