SHOPPING

Прогулка по магазинам
SHOPPING

Описание
Однажды, решив пообедать, вы обнаружили, что ваш холодильник пуст. Так как голодать вам не захотелось, вы решили совершить небольшую прогулку по магазинам и пополнить свои запасы. Вы составили себе записку со списком покупок, в котором получилось N (0<N<=5) записей. Каждый вид еды помечен заглавной буквой латинского алфавита {'A'..'Z'}. Все магазины в городе славятся тем, что ассортимент и наличие товаров в них никогда не меняются.

Задача
Итак, зная полный план города со всеми магазинами и ассортиментом товара в них, вы должные совершить покупки и вернуться домой за минимальное время. Так же известно, что каждый вид еды продается не более чем в 6 магазинах и при покупке снижает вашу скорость на 10% от первоначальной. Временем на покупку товара можно пренебречь.

Формат входных данных
Входной файл SHOPPING.IN содержит:

S
N
X₁X₂..X_NE
M

A₁ B₁ С₁… A_M B_M C_MK
Z₁ Z₂... Z_KY₁₁Y₁₂ ..
...
Y_K1Y_K2 ..

HOUSE

- ваша первоначальная скорость (метров/мин) (0<S<=100, целое)
- количество видов еды, которые необходимо купить
- N различных символов {'A'..'Z'}, обозначающих необходимые виды
- количество зданий в городе (0<E<=100)
- количество дорог соединяющих здания (M<=10000)

- дорога между магазинами A_i и B_i длинны C_i метров (0<Ci<=100). Все дороги двунаправленные

- количество магазинов (K<=E)
- Z_i - номер здания с магазином i

- Y_i1 .. - виды товара в магазине i. Для каждого магазина - одна строка символов {'A'..'Z'}

- номер здания с вашей квартирой

Формат выходных данных
В выходной файл SHOPPING.OUT вывести минимальное затраченное время на покупки, округленное до сотых, либо "Impossible" (без кавычек), если все купить невозможно

Например:

SHOPPING.IN
10
3
BSF
5
7
1 2 1
1 3 20
1 4 1
2 5 1
2 4 10
3 4 10
4 5 1
4
2 3 4 5
BS
B
F
S
1

SHOPPING.OUT
0.47

Пояснение для примера
идем в 4, покупаем F => идем в 5 => идем в 2, покупаем BS => возвращаемся в 1