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 23 92 51 21 22 361 42 43 41 52 53 5
输出复制
9 10 11 9 14 14
输入复制
4 410 10002 51 23 91 21 32 43 492 33 34 14 24 44 54 1014 1024 103
输出复制
5 6 2 5 11 14 10002 10005 10009
输入复制
6 89 54 18 910 49 48 23 54 63 42 31 22 54 51 3103 121 96 472 191 1295 1402 1481 632 433 102
输出复制
10 5 46 10 70 154 81 35 21 109
注意
对于第一个示例中的第三个查询,我们将按以下顺序玩游戏:
- 从顶点 $$$1$$$ 上的交易者那里购买具有 $$$9$$$ 力量的 $$$1$$$ 卡,交易后你仍然会拥有 $$$1$$$ 硬币。
- 从顶点$$$1$$$移动到顶点$$$2$$$。
- 从顶点$$$2$$$移动到顶点$$$3$$$。
- 从顶点$$$3$$$的交易者处购买具有$$$2$$$力量的$$$1$$$卡,交易后你将没有金币。
对于第二个示例中的第五个查询,我们将按以下顺序玩游戏:
- 从顶点$$$1$$$移动到顶点$$$3$$$。
- 从顶点 $$$3$$$ 上的交易者那里购买具有 $$$2$$$ 力量的 $$$1$$$ 卡,交易后你仍然会拥有 $$$3$$$ 硬币。
- 从顶点$$$3$$$移动到顶点$$$4$$$。
- 从顶点$$$4$$$的交易者处购买具有$$$9$$$力量的$$$1$$$卡,交易后你将没有金币。
对于第二个示例中的第六个查询,我们将按以下顺序玩游戏:
- 从顶点$$$1$$$移动到顶点$$$2$$$。
- 从顶点$$$2$$$上的交易者那里购买具有$$$5$$$力量的$$$1$$$卡,交易后你仍然会拥有$$$3$$$硬币。
- 从顶点$$$2$$$移动到顶点$$$4$$$。
- 从顶点$$$4$$$的交易者处购买具有$$$9$$$力量的$$$1$$$卡,交易后你将没有金币。
对于第二个示例中的第七个查询,我们将按以下顺序玩游戏:
- 从顶点 $$$1$$$ 上的交易者那里购买具有 $$$1000$$$ 力量的 $$$10$$$ 卡,交易后你仍然会拥有 $$$1$$$ 硬币。
- 从顶点$$$1$$$移动到顶点$$$3$$$。
- 从顶点$$$3$$$的交易者处购买具有$$$2$$$力量的$$$1$$$卡,交易后你将没有金币。
- 从顶点$$$3$$$移动到顶点$$$4$$$。