题目描述

B 市共有 $m$ 个地铁站，编号为 $1$ 到 $m$。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 $v\ (1 \le v \le m)$ 个地铁站的地铁口走到站厅需要 $w_v$ 的时间。

B 市共有 $n$ 条地铁线路，编号为 $1$ 到 $n$，其中第 $i\ (1 \le i \le n)$ 条线路经过 $k_i$ 个地铁站，编号依次为 $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$。在第 $a_{i,j}\ (1 \le j \le k_i)$ 个地铁站处，从站厅走到第 $i$ 条线路的站台需要 $t_{i,j}$ 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即 $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$ 两两不同。

由于空间有限，每个地铁站最多有 $d$ 条线路经过。此外，B 市的地铁网络是连通的，即任意两个地铁站都可以通过若干条线路互相到达。

小 R 有 $q$ 个出行计划。对于第 $r\ (1 \le r \le q)$ 个出行计划，小 R 将从第 $x_r$ 个地铁站的地铁口出发，乘坐地铁到达第 $y_r$ 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小 R 希望每个出行计划的总步行时间都尽可能少。

你需要帮助小 R 求出，每个出行计划的最小总步行时间。

输入格式

输入的第一行包含五个非负整数 $c, n, m, d, q$，分别表示测试点编号、地铁线路数、地铁站数、每个地铁站最多被几条线路经过，以及出行计划数。特别地，若 $c = 0$，则该测试点为样例。

输入的第二行包含 $m$ 个正整数 $w_1, w_2, \ldots, w_m$。

输入的第 $i + 2\ (1 \le i \le n)$ 行包含 $1 + 2k_i$ 个正整数，其中第一个正整数为 $k_i$；接下来 $2k_i$ 个正整数为 $a_{i,1}, t_{i,1}, a_{i,2}, t_{i,2}, \ldots, a_{i,k_i}, t_{i,k_i}$，其中 $a_{i,j}$ 表示第 $i$ 条线路经过的第 $j$ 个地铁站，$t_{i,j}$ 表示从该地铁站的站厅走到第 $i$ 条线路的站台需要的时间。

输入的第 $r + n + 2\ (1 \le r \le q)$ 行包含两个正整数 $x_r, y_r$，分别表示第 $r$ 个出行计划的起点和终点所在的地铁站编号。

输出格式

输出 $q$ 行，其中第 $r$ 行包含一个非负整数，表示第 $r$ 个出行计划的最小总步行时间。

样例 1

0 2 5 20 2
4 1 9 2 5
3 1 5 2 7 4 6
3 2 3 3 4 5 7
1 3
1 2

32
17

样例 2

0 3 7 20 2
8 3 6 1 7 2 9
3 1 4 2 5 5 100
3 2 6 3 1 7 2
4 3 2 5 100 4 6 6 7
1 6
2 3

35
16

说明

样例 1 解释：第 1 条线路依次经过第 $1, 2, 4$ 个地铁站，第 2 条线路依次经过第 $2, 3, 5$ 个地铁站，两条线路在第 $2$ 个地铁站相交。

对于第 1 个出行计划（$1 \to 3$）：从 1 号站地铁口进站，乘 1 号线到 2 号站，换乘 2 号线到 3 号站后出站，总步行时间为 $w_1 + t_{1,1} + (t_{1,2} + t_{2,2}) + t_{2,3} + w_3 = 4 + 5 + (7 + 3) + 4 + 9 = 32$。

对于第 2 个出行计划（$1 \to 2$）：乘 1 号线直达，总步行时间为 $w_1 + t_{1,1} + t_{1,2} + w_2 = 4 + 5 + 7 + 1 = 17$。

数据范围

对于所有测试数据，均有：

• $0 \le c \le 25$，$1 \le n \le 500$，$1 \le m \le \sum_{i=1}^n k_i \le 5 \times 10^5$，$1 \le d \le 20$，$1 \le q \le 10^5$；
• 对于所有 $v$，$1 \le w_v \le 10^9$；对于所有 $i$，$1 \le k_i \le m$；
• 对于所有 $i, j$，$1 \le a_{i,j} \le m$，$1 \le t_{i,j} \le 10^9$；同一条线路经过的站两两不同；
• 每个地铁站经过的线路数不超过 $d$；任意两个地铁站都可以通过若干条线路互相到达；
• 对于所有 $r$，$1 \le x_r, y_r \le m$，且 $x_r \ne y_r$。

• 特殊性质 A：每条线路至多经过 $2$ 个地铁站，即对于所有 $i$，$k_i \le 2$。
• 特殊性质 B：存在正整数 $T$，使得对于所有 $i, j$，均有 $t_{i,j} = T$。

本题需要文件读写：输入文件 subway.in，输出文件 subway.out。

来源：CSP-S 2026 第二轮 T2。本 OJ 的测试数据为按题面测试点表自造，不是官方数据。本 OJ 内存上限为 512 MiB（原题 1024 MiB）。