#1417. 企鹅物流の礼物

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

龙门一共有 $n$ 家住户，这 $n$ 家住户通过 $m$ 条道路连接形成一个无向图 。

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

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

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

总的来说，一共有 $q$ 天要送货，每天从点 $v_i$ 出发开始送重量为 $w_i$ 的货，只能经过 $w_i \leq k_i$ 的边，经过一个点就可以得到 $a_i$ 的小费，问每天最多能得到多少小费。

第一行三个数 $n$,$m$,$q$。

第二行 $n$ 个数，第 $i$ 个数为 $a_i$。

接下来 $m$ 行，每行三个数 $a$,$b$,$k_i$,表示从 $a$ 到 $b$ 有一条权值为 $k_i$ 的边。

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

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

样例输入

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

$1 \leq n,q \leq 10^5, 1 \leq m \leq 2\times 10 ^ 5$,$1\leq a_i,k_i,w_i \leq 10^6$