← 返回题目
题库练习 Gellyfish and Mayflower
← 上一题 下一题 →

A16605 | Gellyfish and Mayflower

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

May 是 Gellyfish 的朋友，她喜欢玩一款名为“Inscryption”的游戏，这款游戏在一个有向无环图上进行，图中有 $n$ 个顶点和 $m$ 条边。所有的边 $a \rightarrow b$ 都满足 $a<b$。

你从顶点 $1$ 出发，手中有一些金币。你需要沿着有向边从顶点 $1$ 移动到最终 Boss 所在的顶点，然后与最终 Boss 战斗。

图中的每个顶点上都有一位商人，商人会以 $c_i$ 个金币的价格出售一张力量为 $w_i$ 的卡牌。你可以在每个商人处购买任意数量的卡牌，但只有当你当前位于第 $i$ 个顶点时，才能与第 $i$ 个顶点的商人交易。

为了击败 Boss，你希望你持有的卡牌的总力量之和尽可能大。

你需要回答 $q$ 个询问：

- 给定整数 $p$ 和 $r$。如果最终 Boss 位于顶点 $p$，且你一开始有 $r$ 个金币，当你与最终 Boss 战斗时，你能获得的卡牌总力量最大是多少？注意，你可以在顶点 $p$ 处进行交易。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200$，$n-1 \leq m \leq \min(\frac{n(n-1)}{2}, 2000)$），表示顶点数和边数。

接下来的 $n$ 行，每行包含两个整数 $c_i$ 和 $w_i$（$1 \leq c_i \leq 200$，$1 \leq w_i \leq 10^9$），描述第 $i$ 个顶点的商人出售的卡牌。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u < v \leq n$），表示一条从顶点 $u$ 指向顶点 $v$ 的有向边。保证每条边 $(u,v)$ 最多出现一次。

接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示询问的数量。

接下来的 $q$ 行，每行包含两个整数 $p$ 和 $r$（$1 \leq p \leq n$，$1 \leq r \leq 10^9$）。

保证对于所有 $i$，从顶点 $1$ 到顶点 $i$ 都存在一条路径。

输出格式

对于每个询问，输出该询问的答案。

输入输出样例

输入 #1
3 2
3 9
2 5
1 2
1 2
2 3
6
1 4
2 4
3 4
1 5
2 5
3 5
输出 #1
9
10
11
9
14
14
输入 #2
4 4
10 1000
2 5
1 2
3 9
1 2
1 3
2 4
3 4
9
2 3
3 3
4 1
4 2
4 4
4 5
4 101
4 102
4 103
输出 #2
5
6
2
5
11
14
10002
10005
10009
输入 #3
6 8
9 5
4 1
8 9
10 4
9 4
8 2
3 5
4 6
3 4
2 3
1 2
2 5
4 5
1 3
10
3 12
1 9
6 47
2 19
1 129
5 140
2 148
1 63
2 43
3 102
输出 #3
10
5
46
10
70
154
81
35
21
109
C++ 编辑器
输入
输出