Екологічна подорож

Коли ми вирушаємо у відпустку, це часто супроводжується викидами вуглекислого газу. Вартість викидів 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]), округлена до найближчого цілого числа вгору:

Вартість викидів 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.