B. 地铁subway

B 市共有 个地铁站，编号为 到 。每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。从第 （）个地铁站的地铁口走到站厅需要 的时间。

B 市共有 条地铁线路，编号为 到 ，其中第 （）条线路经过 个地铁站，编号依次为 。在第 （）个地铁站处，从站厅走到第 条线路的站台需要 的时间，往返耗时相同。同一条线路不会重复经过同一个地铁站，即 两两不同。

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

小 R 有 个出行计划。对于第 （）个出行计划，小 R 将从第 个地铁站的地铁口出发，乘坐地铁到达第 个地铁站的地铁口，途中可能进行若干次站内换乘。每次站内换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。每个出行计划的总步行时间为进出站和换乘的步行时间之和。小 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

输出 #1

32
17

样例 1 解释

B 市有 个地铁站，从各地铁口走到站厅需要的时间分别为 。

B 市有 条地铁线路，其中第 条线路依次经过第 个地铁站，第 条线路依次经过第 个地铁站，两条线路在第 个地铁站相交。

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

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

输入 #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

输出 #2

35
16

样例 2 解释

B 市有 个地铁站与 条地铁线路，其中第 条线路依次经过第 个地铁站，第 条线路依次经过第 个地铁站，第 条线路依次经过第 个地铁站。

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

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

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

• ，，，，；
• 对于所有 （），均有 ；
• 对于所有 （），均有 ；
• 对于所有 （，），均有 ，；
• 对于所有 （），均有 两两不同；
• 对于所有 （），经过第 个地铁站的线路数均不超过 ；
• 任意两个地铁站都可以通过若干条线路互相到达；
• 对于所有 （），均有 ，且 。

特殊性质 A：每条线路至多经过 个地铁站，即对于所有 （），均有 。

特殊性质 B：对于所有线路经过的所有地铁站，从站厅走到对应线路站台的步行时间都相同，即存在正整数 ，使得对于所有 （，），均有 。