Олег и Сергей − мастера по свету в одном из театров. В их задачу входит управление подсветкой сцены во время спектакля. Спектакль состоит из действий, во время каждого из которых некоторые лампы подсветки должны быть включены, а некоторые выключены. В перерывах между действиями занавес закрывается, и Олег с Сергеем должны включить на сцене набор ламп, необходимый для следующего действия.
Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.
Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.
Кулисы состоят из двух не связанных между собой частей − левой и правой. Левая часть кулис целиком прилегает к левой стороне сцены, а правая − целиком к правой.
Олег может перемещаться по сцене с максимальной скоростью V
1 метров в секунду, а Сергей − V
2 метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.
Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.
Задача Олега и Сергея − организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.
Входные данные
На первой строке входного файла находится пять чисел − W,L,V
1,V
2 и N (1≤W,L≤50, 1≤V
1,V
2≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.
Далее идут N строк с координатами ламп подсветки в метрах x
i,y
i (0<x
i<L, 0<y
i<W).
Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.
Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10
-5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 1 1 3
1 2
3 4
5 3
1
1 3
|
0.000000000000000
|
|
2
|
5 6 1 1 3
1 2
3 4
5 3
3
1 3
2 1 2
3 1 2 3
|
8.828427124746190
|