度假旅行不幸会产生碳足迹。每公里旅行的 $\text{CO}_2$ 排放成本取决于交通方式。例如，火车旅行的成本低于汽车旅行，而汽车旅行的成本又低于其他某些方式。

你的目标是规划一次从你的家（坐标为 $(x_s, y_s)$）到目的地（坐标为 $(x_d, y_d)$）的度假旅行。考虑到旅行对环境的影响，你希望在总行驶距离不超过给定预算 $B$ 的前提下，最小化旅行的 $\text{CO}_2$ 排放成本。

为了辅助规划，你拥有 $N$ 个车站的地图，这些车站可能通过 $T$ 种不同的交通方式（飞机、火车等，编号为 $1, \dots, T$）相互连接。每种交通方式每单位距离的 $\text{CO}_2$ 成本分别为 $C_1, \dots, C_T$。你可以选择乘坐汽车从家到目的地、从家到任意车站，或者从任意车站到目的地，其每单位距离的成本为 $C_0$。$C_0$ 始终大于 $C_1, \dots, C_T$ 中的任何一个。

每个车站 $i$ ($i = 0, \dots, N - 1$) 都有坐标 $(x_i, y_i)$。每个车站可以通过一种或多种交通方式连接到其他车站。每条连接都是双向的，因此只需列出一次。两个车站之间可能存在多种可用的交通方式。你只能通过现有的交通方式在两个车站之间旅行（车站之间不允许乘坐汽车）。

两点 $a$ 和 $b$ 之间的距离是其二维距离向上取整后的整数值：

$$\text{dist}(a, b) = \left\lceil \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2} \right\rceil$$

使用交通方式 $i$ 在 $a$ 和 $b$ 之间旅行的 $\text{CO}_2$ 成本为：

$$\text{cost}(a, b, i) = C_i \times \text{dist}(a, b)$$

给定起点和终点坐标、以距离单位表示的预算 $B$、交通方式列表及其各自的 $\text{CO}_2$ 成本，以及车站网络，你的任务是计算在总行程不超过 $B$ 公里的情况下，可能产生的最小 $\text{CO}_2$ 成本。

输入格式

输入包含以下行： 第 1 行包含两个空格分隔的整数 $x_s$ 和 $y_s$，表示你家的坐标。 第 2 行包含两个空格分隔的整数 $x_d$ 和 $y_d$，表示目的地的坐标。 第 3 行包含一个整数 $B$，表示你可接受的最大旅行距离（单位：公里）。 第 4 行包含一个整数 $C_0$，表示乘坐汽车每单位距离的 $\text{CO}_2$ 成本。 第 5 行包含一个整数 $T$，表示交通方式的数量（不含汽车）。 第 $i+5$ 行（对于 $1 \le i \le T$）包含一个整数 $C_i$，表示交通方式 $i$ 每单位距离的 $\text{CO}_2$ 成本。 第 $T+6$ 行包含一个整数 $N$，表示车站的数量。 第 $i+T+7$ 行（对于 $0 \le i < N$）描述车站 $i$，包含 $3 + 2 \times l_i$ 个空格分隔的整数。前三个整数为 $x_i, y_i$ 和 $l_i$。$(x_i, y_i)$ 表示车站 $i$ 的坐标，$l_i$ 表示车站 $i$ 与其他车站的连接数。随后的 $l_i$ 对整数 $(j, m_j)$ 分别描述了使用交通方式 $m_j$ ($1 \le m_j \le T$) 连接到车站 $j$ ($0 \le j < N$) 的链路。所有链路均为双向。

输出格式

输出应包含一行，即一个整数，表示最小的可行 $\text{CO}_2$ 成本；如果预算内无法到达，则输出 $-1$。

数据范围

所有输入均为整数。所有坐标均在 $[0, 100] \times [0, 100]$ 范围内。 $1 \le T \le 100$ $1 \le N \le 1000$ $0 \le B \le 100$ $1 \le C_1, \dots, C_T < C_0 \le 100$ * 每个车站最多有 100 条连接到其他车站的链路。

样例

样例输入 1

1 1
10 2
12
100
2
10
50
3
2 3 2 1 1 2 2
5 5 1 2 1
9 3 0

样例输出 1

850

说明 1

结果对应于以下路线的 $\text{CO}_2$ 成本： 1. 从家 (1,1) 到车站 0 (2,3)，乘坐汽车，成本为 $100 \times \lceil \sqrt{1^2 + 2^2} \rceil = 300$； 2. 到车站 2 (9,3)，使用交通方式 2，成本为 $50 \times \lceil \sqrt{7^2 + 0^2} \rceil = 350$； 3. 到目的地 (10,2)，乘坐汽车，成本为 $100 \times \lceil \sqrt{1^2 + 1^2} \rceil = 200$，总成本为 850。 该路线有效，因为总行驶距离为 $3 + 7 + 2 = 12$，在允许的预算 12 之内。

Figure 1. 交通方式示意图