时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给定一个有 $n$ 个点，$m$ 条边的有向图。图中第 $i$ 个点的价值是 $v_i$，每条边有一个代价 $z$，不同的边代价可能不一样。

一共有 $q$ 个询问，每次询问包含两个数字 $u, c$，表示询问从 $u$ 点出发，经过代价总和不超过 $c$ 的边所能到达的点的价值总和的最大值。

如果一个点被多次经过，那么其价值要计算多次。初始节点的价值也要计算进去。

输入格式

从标准输入读入数据。

输入的第一行包含三个由空格隔开的正整数 $n, m, q$，保证 $n \le 2000$ 和 $m \le 8000,~q \le 10^5$。

接下来的一行包括 $n$ 个由空格隔开的非负整数 $v_i$ 表示编号从小到大所有点的价值，保证 $v_i \le 10^4$。

接下来的 $m$ 行每行包含三个由空格隔开的正整数 $x, y, z$，保证 $1 \le x, y \le n$ 和 $1 \le z \le 30$，表示存在一条从 $x$ 到 $y$ 代价为 $z$ 的有向边。

接下来的 $q$ 行每行包含两个由空格隔开的非负整数 $u, c$，保证 $1 \le u \le n$ 和 $0 \le c \le 800$。

输出格式

输出到标准输出。

对于每次询问输出一个数，表示相应的答案。

4 4 2
3 2 3 4
1 2 1
2 3 1
3 2 2
3 4 1
2 6
3 2

14
7

样例 1 解释

对于第一个询问最优方案是从 $2$ 出发，经过 $3, 2, 3, 4$ 四个点，取得的价值是 $2 + 3 + 2 + 3 + 4 = 14$。

对于第二个询问最优方案是从 $3$ 出发，经过 $4$ 这个点，取得的价值是 $3 + 4 = 7$。

子任务

对于所有数据，保证：$n \le 2000,~m \le 8000,~c \le 800,~q \le 10^5$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。