← 返回题目列表

Codeforces · 2115/E

E. 水母和五月花

中文机器翻译题面 查看原题
五月花梅花

May,Gellyfish 的朋友,喜欢玩一种名为“Inscryption”的游戏,该游戏是在具有 $$$n$$$ 顶点和 $$$m$$$ 边的有向无环图上玩的。所有边 $$$ a \rightarrow b$$$ 满足 $$$a \lt b$$$。

你从顶点 $$$1$$$ 开始,带着一些硬币。你需要沿着有向边从顶点$$$1$$$移动到boss所在的顶点,然后与最终boss战斗。

图表的每个 $$$n$$$ 顶点都包含一个交易者,他会以 $$$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$$$ 输入行中的第 $$$i$$$ 每行包含两个整数 $$$c_i$$$ 和 $$$w_i$$$ ($$$1 \leq c_i \leq 200$$$, $$$1 \leq w_i \leq 10^9$$$) — 描述交易者的牌第 $$$i$$$ 个顶点。

在接下来的 $$$m$$$ 行输入中,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u \lt v \leq n$$$),表示从顶点 $$$u$$$ 到顶点 $$$v$$$ 的有向边。保证每条边 $$$(u,v)$$$ 最多出现一次。

下一行输入包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

在以下 $$$q$$$ 输入行中,每行包含两个整数 $$$p$$$ 和 $$$r$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq r \leq 10^9$$$)。

保证对于所有$$$i$$$,存在从顶点$$$1$$$到顶点$$$i$$$的路径。

输出

对于每个查询,输出查询的答案。

示例

输入
复制

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

输出
复制

9
10
11
9
14
14

输入
复制

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

输出
复制

5
6
2
5
11
14
10002
10005
10009

输入
复制

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

输出
复制

10
5
46
10
70
154
81
35
21
109

注意

对于第一个示例中的第三个查询,我们将按以下顺序玩游戏:

  • 从顶点 $$$1$$$ 上的交易者那里购买具有 $$$9$$$ 力量的 $$$1$$$ 卡,交易后你仍然会拥有 $$$1$$$ 硬币。
  • 从顶点$$$1$$$移动到顶点$$$2$$$。
  • 从顶点$$$2$$$移动到顶点$$$3$$$。
  • 从顶点$$$3$$$的交易者处购买具有$$$2$$$力量的$$$1$$$卡,交易后你将没有金币。
最终,我们将拥有$$$1$$$卡,力量$$$9$$$,$$$1$$$卡,力量$$$2$$$,所以卡片力量之和为$$$9+2=11$$$。

对于第二个示例中的第五个查询,我们将按以下顺序玩游戏:

  • 从顶点$$$1$$$移动到顶点$$$3$$$。
  • 从顶点 $$$3$$$ 上的交易者那里购买具有 $$$2$$$ 力量的 $$$1$$$ 卡,交易后你仍然会拥有 $$$3$$$ 硬币。
  • 从顶点$$$3$$$移动到顶点$$$4$$$。
  • 从顶点$$$4$$$的交易者处购买具有$$$9$$$力量的$$$1$$$卡,交易后你将没有金币。
最终,我们将拥有$$$1$$$卡,功率为$$$2$$$,$$$1$$$卡为$$$9$$$,因此卡的功率总和为$$$2+9=11$$$。

对于第二个示例中的第六个查询,我们将按以下顺序玩游戏:

  • 从顶点$$$1$$$移动到顶点$$$2$$$。
  • 从顶点$$$2$$$上的交易者那里购买具有$$$5$$$力量的$$$1$$$卡,交易后你仍然会拥有$$$3$$$硬币。
  • 从顶点$$$2$$$移动到顶点$$$4$$$。
  • 从顶点$$$4$$$的交易者处购买具有$$$9$$$力量的$$$1$$$卡,交易后你将没有金币。
最终,我们将拥有$$$1$$$卡,力量$$$5$$$,$$$1$$$卡,力量$$$9$$$,所以卡片力量之和为$$$5+9=14$$$。

对于第二个示例中的第七个查询,我们将按以下顺序玩游戏:

  • 从顶点 $$$1$$$ 上的交易者那里购买具有 $$$1000$$$ 力量的 $$$10$$$ 卡,交易后你仍然会拥有 $$$1$$$ 硬币。
  • 从顶点$$$1$$$移动到顶点$$$3$$$。
  • 从顶点$$$3$$$的交易者处购买具有$$$2$$$力量的$$$1$$$卡,交易后你将没有金币。
  • 从顶点$$$3$$$移动到顶点$$$4$$$。
最终,我们将拥有$$$10$$$卡,力量$$$1000$$$,$$$1$$$卡,力量$$$2$$$,所以卡的力量总和是$$$10 \cdot 1000+2=10\,002$$$。