人生是一场游戏。

世界可以被看作是一个包含 $n$ 个城市和 $m$ 条连接城市间的无向道路的连通图。现在，作为人生游戏玩家的你，将在世界图上进行游戏。

最初，你位于第 $x$ 个城市，拥有 $k$ 点社交能力值。你可以通过在城市中生活和工作来赚取社交能力值。具体来说，在第 $i$ 个城市生活和工作可以获得 $a_i$ 点社交能力值。但在本题中，你不能在同一个城市重复获得社交能力值，因此你需要游历世界以赚取更多的社交能力值。然而，道路并不容易通行。具体而言，第 $i$ 条道路有一个能力阈值 $w_i$，你必须拥有至少 $w_i$ 点社交能力值才能通过该道路。此外，你的社交能力值在通过道路时不会减少，只需在想要通过第 $i$ 条道路时满足至少 $w_i$ 点的要求即可。

正如你所见，人生游戏就是不断地生活、工作和旅行。游戏共有 $q$ 个存档。对于每个存档，给出了初始城市和初始社交能力值，且玩家尚未在任何城市生活或工作过。现在，作为真实的人生游戏玩家，你需要确定在游戏结束时你可能拥有的最大社交能力值，并为每个给定的存档输出该值。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le n, m, q \le 10^5$)，分别表示城市数量、道路数量和游戏存档数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$)，表示各城市提供的社交能力奖励值。

接下来的 $m$ 行，每行包含三个整数 $u, v, w$ ($1 \le u < v \le n, 1 \le w \le 10^9$)，表示城市 $u$ 和 $v$ 之间存在一条能力阈值为 $w$ 的无向道路。

接下来的 $q$ 行，每行包含两个整数 $x, k$ ($1 \le x \le n, 1 \le k \le 10^9$)，表示游戏存档。

输出格式

对于每个游戏存档，输出一行，包含一个整数，表示你最终可能拥有的最大社交能力值。

样例

输入 1

8 10 2
3 1 4 1 5 9 2 6
1 2 7
1 3 11
2 3 13
3 4 1
3 6 31415926
4 5 27182818
5 6 1
5 7 23333
5 8 55555
7 8 37
1 7
8 30

输出 1

16
36

说明

下图展示了给定的图：

• 对于第一个游戏存档，你可以到达 4 个城市 $\{1, 2, 3, 4\}$，最终拥有 $7 + 3 + 1 + 4 + 1 = 16$ 点社交能力值。
• 对于第二个游戏存档，你只能到达初始城市 $\{8\}$，最终拥有 $30 + 6 = 36$ 点社交能力值。