시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Олег и Сергей --- мастера по свету в одном из театров. В их задачу входит управление подсветкой сцены во время спектакля. Спектакль состоит из действий, во время каждого из которых некоторые лампы подсветки должны быть включены, а некоторые выключены. В перерывах между действиями занавес закрывается, и Олег с Сергеем должны включить на сцене набор ламп, необходимый для следующего действия.
Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.
Театральная сцена представляет собой прямоугольник $W$ на $L$ метров, внутри которого расположено $N$ ламп подсветки.
Кулисы состоят из двух не связанных между собой частей --- левой и правой. Левая часть кулис целиком прилегает к левой стороне сцены, а правая --- целиком к правой.
Олег может перемещаться по сцене с максимальной скоростью $V_1$ метров в секунду, а Сергей --- $V_2$ метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.
Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий $M$ и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей --- в правой. Изначально включены лампы, необходимые для первого действия.
Задача Олега и Сергея --- организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.
На первой строке входного файла находится пять чисел --- $W, L, V_1, V_2$ и $N$ ($1 \le W, L \le 50$, $1 \le V_1, V_2 \le 20$, $1 \le N \le 15$) --- размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно. Далее идут $N$ строк с координатами ламп подсветки в метрах $x_i, y_i$ ($0 < x_i < L$, $0 < y_i < W$). Следующая строка содержит число $M$ ($1 \le M \le 10\,000$) --- число действий в спектакле. Далее идут $M$ строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.
В выходной файл выведите единственное число --- минимальное суммарное время перерывов между действиями в секундах с точностью $10^{-5}$.
5 6 1 1 3 1 2 3 4 5 3 1 1 3
0.000000
5 6 1 1 3 1 2 3 4 5 3 3 1 3 2 1 2 3 1 2 3
8.828427
В первом примере только одно действие, поэтому суммарное время перерывов равно нулю.