G. 企鹅物流の礼物

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

众所周知,企鹅物流是龙门的一家正经的物流运输公司。

龙门一共有 家住户,这 家住户通过 条道路连接形成一个无向图

正值愚人节这几天,企鹅物流的老板 大帝为了庆祝他的演唱会顺利进行,准备每天给龙门的每一位住户发放企鹅物流的精美小礼品,这可把德克萨斯愁坏了,这么多的礼物怎么送的完。

但是幸运的是,龙门这几天开交通管制,每条边有一个权值 , 只有重量 的货可以通过。这可把德克萨斯高兴坏了,这下子他可以摸鱼了。

龙门人非常的慷慨,虽然是免费送的小礼品,但是他们会回报 的小费,德克萨斯想得到尽可能多的小费。

总的来说,一共有 天要送货,每天从点 出发开始送重量为 的货,只能经过 的边,经过一个点就可以得到 的小费,问每天最多能得到多少小费。

输入格式

第一行三个数 ,,

第二行 个数,第 个数为

接下来 行,每行三个数 ,,,表示从 有一条权值为 的边。

接下来 行,每行两个数 ,,表示每天送货的起始地点,送货重量。

输出格式

对于每组询问,输出一个整数表示每天最多能得到多少小费。

样例

样例输入

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5
1 1
6 2
8 9

样例输出

3
55
55
25

数据范围与提示

,