환경 친화적 여행

휴가를 다녀오면 탄소 발자국이 남는다. 1킬로미터를 이동할 때 발생하는 CO2 비용은 교통수단에 따라 다르다. 예를 들어 기차는 버스보다 비용이 적고, 버스는 자동차보다 비용이 적다.

집의 좌표가 (xs, ys)이고 여행 목적지의 좌표가 (xd, yd)일 때, 집에서 목적지까지 가는 휴가 여행을 계획하려 한다. 여행이 환경에 미치는 영향을 알고 있으므로 CO2 비용을 최소화하고 싶지만, 이동한 총 킬로미터 수는 주어진 예산 B 이내로 유지해야 한다.

계획을 세우는 데 도움이 되도록 N개의 역으로 이루어진 지도가 주어진다. 역들은 T가지 교통수단(비행기, 기차 등)으로 연결될 수 있으며, 교통수단은 1, . . . , T로 번호가 붙어 있다. 각 교통수단의 단위 거리당 CO2 비용은 C1, . . . , CT이다. 자동차로는 집에서 목적지까지, 집에서 임의의 역까지, 임의의 역에서 목적지까지 이동할 수 있으며, 이때 단위 거리당 비용은 C0이다. C0은 항상 C1, . . . , CT보다 크다.

N개의 역 각각의 좌표는 (xi, yi)이다(단, i = 0, . . . , N − 1). 각 역은 T가지 교통수단 중 하나 또는 여러 개로 다른 역과 연결될 수 있다. 모든 연결은 양방향이므로 한 방향만 주어진다. 두 역 사이에 여러 교통수단이 있을 수 있다. 두 역 사이는 연결된 교통수단으로만 이동할 수 있으며, 역 사이에서는 자동차를 이용할 수 없다.

두 점 a와 b 사이의 거리는 (xa, ya)와 (xb, yb) 사이의 2D 거리를 올림한 정수이다.

dist(a, b) = ⌈√((xa - xb)2 + (ya - yb)2)⌉,

교통수단 i로 a와 b 사이를 이동할 때의 CO2 비용은 다음과 같다.

cost(a, b, i) = Ci × dist(a, b).

출발지와 목적지의 좌표, 거리 단위로 주어진 예산 B, 교통수단 목록과 각 교통수단의 CO2 비용, 역 네트워크가 주어졌을 때, 최대 B킬로미터 이내로 이동하면서 가능한 최소 CO2 비용을 계산하라.

입력은 다음 줄로 이루어진다.

• 1번째 줄에는 집의 좌표 xs와 ys가 공백으로 구분되어 주어진다.
• 2번째 줄에는 목적지의 좌표 xd와 yd가 공백으로 구분되어 주어진다.
• 3번째 줄에는 이동할 수 있는 최대 거리(킬로미터) B가 주어진다.
• 4번째 줄에는 자동차로 이동할 때 단위 거리당 CO2 비용 C0이 주어진다.
• 5번째 줄에는 자동차를 제외한 교통수단의 수 T가 주어진다.
• i + 5번째 줄에는 1 ≤ i ≤ T인 교통수단 i의 단위 거리당 CO2 비용 Ci가 주어진다.
• T + 6번째 줄에는 역의 수 N이 주어진다.
• i + T + 7번째 줄에는 역 i(0 ≤ i < N)가 주어지며, 3 + 2 × li개의 정수가 공백으로 구분되어 있다. 처음 세 정수는 xi, yi, li이다. (xi, yi)는 역 i의 좌표이고, li는 역 i와 다른 역 사이의 연결 수이다. 나머지 li개의 정수 쌍 (j, mj)은 각각 교통수단 mj(1 ≤ mj ≤ T)를 사용해 역 j(0 ≤ j < N)로 가는 연결을 나타낸다. 모든 연결은 양방향이다.

가능한 최소 CO2 비용을 나타내는 정수 하나를 한 줄에 출력한다. 킬로미터 예산 이내에서 가능한 비용이 없으면 −1을 출력한다.

모든 입력은 정수이다. 모든 좌표는 [0, 100] × [0, 100] 범위에 있다.

• 1 ≤ T ≤ 100;
• 1 ≤ N ≤ 1 000;
• 0 ≤ B ≤ 100;
• 1 ≤ C1, . . . , CT < C0 ≤ 100;
• 각 역에 대해 다른 역으로 가는 연결은 최대 100개이다.

결과는 다음 경로의 CO2 비용에 해당한다.

1. (1,1)의 집에서 (2,3)의 역 0으로 자동차를 타고 이동하며 비용은 100 × ⌈√(12 + 22)⌉ = 300,
2. 교통수단 2를 사용해 (9,3)의 역 2로 이동하며 비용은 50 × ⌈√(72 + 02)⌉ = 350,
3. (10,2)의 목적지로 자동차를 타고 이동하며 비용은 100 × ⌈√(12 + 12)⌉ = 200이고, 총합은 850이다.

이 경로는 총 이동 거리가 3 + 7 + 2 = 12로 허용 예산 12 이내이므로 유효하다.