CFCF2115E.Gellyfish and Mayflower

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$ 的商人处购买 $1$ 张力量为 $9$ 的卡牌，交易后你还剩 $1$ 个金币。
• 从顶点 $1$ 移动到顶点 $2$。
• 从顶点 $2$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量为 $2$ 的卡牌，交易后你没有金币了。

最终，你拥有 $1$ 张力量为 $9$ 的卡牌和 $1$ 张力量为 $2$ 的卡牌，总力量为 $9+2=11$。

对于第二个样例的第五个询问，游戏过程如下：

• 从顶点 $1$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量为 $2$ 的卡牌，交易后你还剩 $3$ 个金币。
• 从顶点 $3$ 移动到顶点 $4$。
• 在顶点 $4$ 的商人处购买 $1$ 张力量为 $9$ 的卡牌，交易后你没有金币了。

最终，你拥有 $1$ 张力量为 $2$ 的卡牌和 $1$ 张力量为 $9$ 的卡牌，总力量为 $2+9=11$。

对于第二个样例的第六个询问，游戏过程如下：

• 从顶点 $1$ 移动到顶点 $2$。
• 在顶点 $2$ 的商人处购买 $1$ 张力量为 $5$ 的卡牌，交易后你还剩 $3$ 个金币。
• 从顶点 $2$ 移动到顶点 $4$。
• 在顶点 $4$ 的商人处购买 $1$ 张力量为 $9$ 的卡牌，交易后你没有金币了。

最终，你拥有 $1$ 张力量为 $5$ 的卡牌和 $1$ 张力量为 $9$ 的卡牌，总力量为 $5+9=14$。

对于第二个样例的第七个询问，游戏过程如下：

• 在顶点 $1$ 的商人处购买 $10$ 张力量为 $1000$ 的卡牌，交易后你还剩 $1$ 个金币。
• 从顶点 $1$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量为 $2$ 的卡牌，交易后你没有金币了。
• 从顶点 $3$ 移动到顶点 $4$。

最终，你拥有 $10$ 张力量为 $1000$ 的卡牌和 $1$ 张力量为 $2$ 的卡牌，总力量为 $10 \cdot 1000+2=10\,002$。