You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目内容】

牛牛最近在为自己的出行烦忧。

牛牛所在的城市可以简化为 n个点，编号从 1 开始。由 m 条无向边表达两两之间的路径。第 i 条边连通点 ui和vi，距离为di。牛牛是个懒人，他宁愿叫出租车也不愿意走路。牛牛所在城市的出租车不计算起步价，直接按照距离计费，每 r单位距离 1 元，向上取整，即如果单次行进了 p 单位距离，将收费 元。如果多次乘坐分开收费。

牛牛所在的城市还有 k 路不同的公交车，每一路公交车都是双向的，有 ti个站台，可以正着坐，也可以反着坐，但每路公交车仅会在规定的站台停车。牛牛从任意一个位置上车，可以从该路公交车的任意站台下车，仅需付一份该路的公交车车费ci元。但坐到终点站之后必须下车。

牛牛有q 个规划，其中第i个规划为从ai位置移动到bi 位置，牛牛想知道这样的移动最小需要的花费是多少。花费是指出租车的花费和公交车的花费之和。

【输入格式】

第一行输入五个整数 n,m,k,r,q，分别表示牛牛所在的城市的点数，边数，公交车

有多少路，出租车收费标准和规划次数。

第二行起 m 行，第 i 行三个整数ui,vi,di，表示对应的边连接ui和vi，距离为di。

随后 k 行，每行第一个整数表示对应路公交车的站台数目。第二个整数表示该路公交车的收费。随后个整数，分别表示该路公交车停的站台。

随后 q 行，第 i 行两个整数, 表示牛牛计划从到，想知道其最小花费。

【输出格式】

输出 q 行，每行一个整数，表示第 i 个规划的答案。

【样例 1 输入】

5 6 1 10 5

1 2 15

2 3 177

3 5 73

4 2 37

1 5 66

1 4 43

3 11 1 3 5

1 2

1 4

1 3

4 5

2 3

【样例 1 输出】

2

5

11

11

13

【样例解释】

1 到 2 直接打车，花费 15/10 向上取整，花费为 2。

1 到 4 直接打车，花费 43/10 向上取整，花费为 5。

1 到 3 直接坐公交车，花费为 11。

4 到 5 直接打车，从 4 到 1 到 5，花费 109/10 向上取整，花费为 11。

2 到 3 先打车到 1，花费 2，再坐公交车到 3，花费 11，共计花费 13。

【数据规模】