Экологичное путешествие

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

Ваша цель состоит в том, чтобы спланировать поездку на каникулы из Вашего дома, заданного координатами (x[s], y[s]), до пункта назначения с координатами (x[d], y[d]). Осознавая влияние путешествия на окружающую среду, Вы хотите свести к минимуму расходы на выбросы CO2 во время отпуска, но все же хотите сохранить общее количество пройденных километров в рамках заданного бюджета B.

Чтобы помочь в планировании, у Вас есть доступ к карте n станций, возможно связанных t различными видами транспорта (самолет, поезд и так далее), пронумерованными 1, ... , t. У каждого вида транспорта есть единицы измерения стоимости CO2 на расстояние c[1], ..., c[t]. Вы можете путешествовать на машине от Вашего дома до пункта назначения, от Вашего дома до любой станции и от любой станции до пункта назначения по цене c[0] за единицу расстояния. c[0] всегда больше любого из c[1], ..., c[t].

Каждая из n станций имеет координаты (x[i], y[i]) для i = 0, ..., n - 1. Каждая станция может быть связана с другими станциями через один или несколько видов транспорта t. Каждое соединение работает в обе стороны, поэтому необходимо указать только одно направление. Между двумя станциями может быть несколько видов транспорта. Вы можете перемещаться между двумя станциями только через их соединения, используя доступные виды транспорта (проезд на автомобиле между станциями запрещен).

Расстояние между двумя точками a и b - это расстояние на плоскости между (x[a], y[a]) и (x[b], y[b]), округленное до ближайшего целого числа вверх:

а стоимость CO2 при проезде между a и b с использованием вида транспорта i составляет:

cost(a, b, i) = c[i] * dist(a, b)

Имея две координаты источник - пункт назначения, бюджет B, выраженный в единицах расстояния, список видов транспорта и их соответствующие затраты на выбросы CO2, а также сеть станций, Ваша задача состоит в том, чтобы вычислить минимально возможные затраты на выбросы CO2 во время путешествия не более чем на B километров.

Входные данные

Состоит из следующих строк:

• Строка 1 содержит два целых числа, разделенных пробелом, x[s] и y[s], координаты Вашего дома.

• Строка 2 содержит два целых числа, разделенных пробелом, x[d] и y[d], координаты Вашего пункта назначения.

• Строка 3 содержит целое число B (0 ≤ B ≤ 100), максимальное расстояние (в километрах), которое Вы соглашаетесь проехать.

• Строка 4 содержит целое число c[0], стоимость CO2 на единицу расстояния проезда на машине.

• Строка 5 содержит целое число t (1 ≤ t ≤ 100), количество видов транспорта (кроме автомобилей).

• Строка i + 5, для 1 ≤ i ≤ t, содержит целое число c[i], стоимость CO2 на единицу расстояния вида транспорта i (1 ≤ c[1], ..., c[t] < c[0] ≤ 100).

• Строка t + 6 содержит целое число n (1 ≤ n ≤ 1000), количество станций.

• Строка i + t + 7 описывает станцию i (0 ≤ i < n) и содержит 3 + 2 * l[i] целых чисел, разделенных пробелами. Первые три целых числа - это x[i], y[i] и l[i]. Пара (x[i], y[i]) представляет координаты станции i, а l[i] - количество соединений между станцией i и другими станциями. Каждая из остальных l[i] пар целых чисел (j, m[j]) описывает соединение со станцией j (0 ≤ j < n) с использованием вида транспортировки m[j] (1 ≤ m[j] ≤ t). Все соединения двунаправленные.

Все входные данные целые. Все координаты принадлежат области [0, 100] * [0, 100]. Для каждой станции имеется не более 100 соединений с другими станциями.

Выходные данные

Выведите одно целое число, представляющее минимально возможные затраты на выбросы CO2, или -1, если в пределах километража нет приемлиемой стоимости.

Примеры

Примечание

Результаты соответствуют стоимости CO2 на следующем маршруте:

1. от дома в (1, 1) до станции 0 в (2, 3) на машине по цене 100 * sqrt(1^2 + 2^2) = 300,

2. до станции 2 в (9, 3) видом транспорта 2 по цене 50 * sqrt(7^2 + 0^2) = 350,

3. до пункта назначения в (10, 2) на машине по цене 100 * sqrt(1^2 + 1^2) = 200. Общая сумма 850.

Этот маршрут действителен, поскольку общее пройденное расстояние составляет 3 + 7 + 2 = 12 в пределах допустимого бюджета 12.