B. 地铁 / subway
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 求出，每个出行计划的最小总步行时间。

Input

从标准输入读入数据。

输入的第一行包含五个非负整数 $$$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$$$，表示第 $$$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$$$ 个出行计划的起点和终点所在的地铁站编号。

Output

输出到标准输出。

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

Examples
Input
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
Output
32
17
Input
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
Output
35
16
Note

补充样例文件可从原题页面的附件下载：https://www.luogu.com.cn/problem/P17832。

样例 1 解释

B 市有 $$$5$$$ 个地铁站，从各地铁口走到站厅需要的时间分别为 $$$4,1,9,2,5$$$。

B 市有 $$$2$$$ 条地铁线路，其中第 $$$1$$$ 条线路依次经过第 $$$1,2,4$$$ 个地铁站，第 $$$2$$$ 条线路依次经过第 $$$2,3,5$$$ 个地铁站，两条线路在第 $$$2$$$ 个地铁站相交。

对于第 $$$1$$$ 个出行计划，小 R 将从第 $$$1$$$ 个地铁站前往第 $$$3$$$ 个地铁站：他可以先从第 $$$1$$$ 个地铁站的地铁口走到站厅，再走到第 $$$1$$$ 条线路的站台，乘坐第 $$$1$$$ 条线路到达第 $$$2$$$ 个地铁站后走回站厅，再走到第 $$$2$$$ 条线路的站台，乘坐第 $$$2$$$ 条线路到达第 $$$3$$$ 个地铁站后走回站厅，最后走到第 $$$3$$$ 个地铁站的地铁口，总步行时间为

$$$$$$ w_1+t_{1,1}+(t_{1,2}+t_{2,1})+t_{2,2}+w_3=4+5+(7+3)+4+9=32. $$$$$$

对于第 $$$2$$$ 个出行计划，小 R 将从第 $$$1$$$ 个地铁站前往第 $$$2$$$ 个地铁站：他可以先从第 $$$1$$$ 个地铁站的地铁口走到站厅，再走到第 $$$1$$$ 条线路的站台，乘坐第 $$$1$$$ 条线路到达第 $$$2$$$ 个地铁站后走回站厅，最后走到第 $$$2$$$ 个地铁站的地铁口，总步行时间为

$$$$$$ w_1+t_{1,1}+t_{1,2}+w_2=4+5+7+1=17. $$$$$$

样例 2 解释

B 市有 $$$7$$$ 个地铁站与 $$$3$$$ 条地铁线路，其中第 $$$1$$$ 条线路依次经过第 $$$1,2,5$$$ 个地铁站，第 $$$2$$$ 条线路依次经过第 $$$2,3,7$$$ 个地铁站，第 $$$3$$$ 条线路依次经过第 $$$3,5,4,6$$$ 个地铁站。

对于第 $$$1$$$ 个出行计划，小 R 将从第 $$$1$$$ 个地铁站前往第 $$$6$$$ 个地铁站：他可以先从第 $$$1$$$ 个地铁站的地铁口走到站厅，再走到第 $$$1$$$ 条线路的站台，乘坐第 $$$1$$$ 条线路到达第 $$$2$$$ 个地铁站后走回站厅，再走到第 $$$2$$$ 条线路的站台，乘坐第 $$$2$$$ 条线路到达第 $$$3$$$ 个地铁站后走回站厅，再走到第 $$$3$$$ 条线路的站台，乘坐第 $$$3$$$ 条线路到达第 $$$6$$$ 个地铁站后走回站厅，最后走到第 $$$6$$$ 个地铁站的地铁口，总步行时间为

$$$$$$ w_1+t_{1,1}+(t_{1,2}+t_{2,1})+(t_{2,2}+t_{3,1})+t_{3,4}+w_6=35. $$$$$$

对于第 $$$2$$$ 个出行计划，小 R 将从第 $$$2$$$ 个地铁站前往第 $$$3$$$ 个地铁站：他可以先从第 $$$2$$$ 个地铁站的地铁口走到站厅，再走到第 $$$2$$$ 条线路的站台，乘坐第 $$$2$$$ 条线路到达第 $$$3$$$ 个地铁站后走回站厅，最后走到第 $$$3$$$ 个地铁站的地铁口，总步行时间为

$$$$$$ w_2+t_{2,1}+t_{2,2}+w_3=16. $$$$$$

样例 3

见题目目录下的 subway/3.in 与 subway/3.ans。

该样例满足测试点 $$$4 \sim 6$$$ 的约束条件。

样例 4

见题目目录下的 subway/4.in 与 subway/4.ans。

该样例满足测试点 $$$9 \sim 11$$$ 的约束条件。

样例 5

见题目目录下的 subway/5.in 与 subway/5.ans。

该样例满足测试点 $$$12 \sim 15$$$ 的约束条件。

样例 6

见题目目录下的 subway/6.in 与 subway/6.ans。

该样例满足测试点 $$$16 \sim 19$$$ 的约束条件。

样例 7

见题目目录下的 subway/7.in 与 subway/7.ans。

该样例满足测试点 $$$22,23$$$ 的约束条件。

数据范围

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

  • $$$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 v \le m$$$），均有 $$$1 \le w_v \le 10^9$$$；
  • 对于所有 $$$i$$$（$$$1 \le i \le n$$$），均有 $$$1 \le k_i \le m$$$；
  • 对于所有 $$$i,j$$$（$$$1 \le i \le n$$$，$$$1 \le j \le k_i$$$），均有 $$$1 \le a_{i,j} \le m$$$，$$$1 \le t_{i,j} \le 10^9$$$；
  • 对于所有 $$$i$$$（$$$1 \le i \le n$$$），均有 $$$a_{i,1},a_{i,2},\ldots,a_{i,k_i}$$$ 两两不同；
  • 对于所有 $$$v$$$（$$$1 \le v \le m$$$），经过第 $$$v$$$ 个地铁站的线路数均不超过 $$$d$$$；
  • 任意两个地铁站都可以通过若干条线路互相到达；
  • 对于所有 $$$r$$$（$$$1 \le r \le q$$$），均有 $$$1 \le x_r,y_r \le m$$$，且 $$$x_r \ne y_r$$$。
测试点编号$$$n \le$$$$$$\sum_{i=1}^{n} k_i \le$$$$$$d \le$$$$$$q \le$$$特殊性质
$$$1 \sim 3$$$$$$3$$$$$$10$$$$$$20$$$$$$10$$$无
$$$4 \sim 6$$$$$$50$$$$$$300$$$$$$20$$$$$$200$$$无
$$$7,8$$$$$$200$$$$$$400$$$$$$20$$$$$$200$$$A
$$$9 \sim 11$$$$$$500$$$$$$1000$$$$$$20$$$$$$10^5$$$A
$$$12 \sim 15$$$$$$500$$$$$$2 \times 10^4$$$$$$20$$$$$$2000$$$B
$$$16 \sim 19$$$$$$500$$$$$$5 \times 10^5$$$$$$20$$$$$$10^5$$$B
$$$20,21$$$$$$2$$$$$$5 \times 10^5$$$$$$20$$$$$$10^5$$$无
$$$22,23$$$$$$500$$$$$$5 \times 10^5$$$$$$2$$$$$$10^5$$$无
$$$24,25$$$$$$500$$$$$$5 \times 10^5$$$$$$20$$$$$$10^5$$$无

特殊性质 A：每条线路至多经过 $$$2$$$ 个地铁站，即对于所有 $$$i$$$（$$$1 \le i \le n$$$），均有 $$$k_i \le 2$$$。

特殊性质 B：对于所有线路经过的所有地铁站，从站厅走到对应线路站台的步行时间都相同，即存在正整数 $$$T$$$，使得对于所有 $$$i,j$$$（$$$1 \le i \le n$$$，$$$1 \le j \le k_i$$$），均有 $$$t_{i,j}=T$$$。

本题满分 100 分。官方测试点共 25 个，每个测试点 4 分，独立计分。展示样例中，与官方测试点完全相同的样例保留原测试点分值；其余样例不计分。