题目描述 给定一个有 $n$ 个点，$m$ 条边的有向图。 图中第 $i$ 个点的价值是 $v i$，每条边有一个代价 $z$，不同的边代价可能不一样。 一共有 $q$ 个询问，每次询问包含两个数字 $u, c$，表示询问从 $u$ 点出发，经过代价总和不超过 $c$ 的边所能到达的点的价值总和的最大值。 如果一个点被多次经过，那么其价值要计算多次。 初始节点的价值也要计算进去。 输入格式 第一行包含三个由空格隔开的正整数 $n, m, q$。 接下来的一行包括 $n$ 个由空格隔开的非负整数 $v i$，表示编号从小到大所有点的价值。 接下来的 $m$ 行每行包含三个由空格隔开的正整数 $x, y, z$，表示存在一条从 $x$ 到 $y$ 代价为 $z$ 的有向边。 接下来的 $q$ 行每行包含两个由空格隔开的非负整数 $u, c$，表示每次询问的起点 $u$ 和最大代价 $c$。 输出格式 对于每次询问输出一个数，表示相应的答案。 输入样例 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