U276868 图

**时间限制：** 1.0 秒 **空间限制：** 512 MB

给定一个有 $n$ 个点，$m$ 条边的有向图。图中第 $i$ 个点的价值是 $v_i$，每条边有一个代价 $z$，不同的边代价可能不一样。 一共有 $q$ 个询问，每次询问包含两个数字 $u, c$，表示询问从 $u$ 点出发，经过代价总和不超过 $c$ 的边所能到达的点的价值总和的最大值。 如果一个点被多次经过，那么其价值要计算多次。初始节点的价值也要计算进去。

无

无

### 样例 1 解释 对于第一个询问最优方案是从 $2$ 出发，经过 $3, 2, 3, 4$ 四个点，取得的价值是 $2 + 3 + 2 + 3 + 4 = 14$ 。 对于第二个询问最优方案是从 $3$ 出发，经过 $4$ 这个点，取得的价值是 $3 + 4 = 7$ 。 ### 子任务 |编号|分值|特殊性质| |:---:|:---:|:---:| |1|17|$n \le 5,~m \le 10,~c \le 8,~q \le 8$| |2|23|$u = 1$| |3|25|$q \le 5$| |4|35|$n \le 2000,~m \le 8000,~c \le 800,~q \le 10^5$| 对于所有子任务，保证：$n \le 2000,~m \le 8000,~c \le 800,~q \le 10^5$ 。