E. 水母与五月花号

时间限制： 3 秒
内存限制： 1024 MB

五月花号 by Plum

五月份，水母的朋友 May 喜欢玩一个名为“Inscryption”的游戏，该游戏在一个有 $n$ 个顶点、$m$ 条边的有向无环图上进行。所有边 $a \rightarrow b$ 都满足 $a < b$。

你从顶点 $1$ 出发，携带一定数量的硬币。你需要沿着有向边从顶点 $1$ 移动到最终首领所在的顶点，然后与最终首领战斗。

图上的每个顶点 $i$ 都有一个商人，他会以 $c_i$ 枚硬币的价格卖给你一张威力值为 $w_i$ 的卡牌。你可以从每个商人处购买任意数量的卡牌。但是，你只有在当前位于顶点 $i$ 时，才能与该顶点的商人交易。

为了击败首领，你希望自己拥有的卡牌的威力值之和尽可能大。

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

给定整数 $p$ 和 $r$。如果最终首领位于顶点 $p$，并且你一开始有 $r$ 枚硬币，当你与最终首领战斗时，你的卡牌威力值之和的最大值是多少？注意，允许在顶点 $p$ 处也进行卡牌交易。

---

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 200$，$n-1 \le m \le \min\left(\frac{n(n-1)}{2}, 2000\right)$）—— 图中顶点数和边数。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $c_i$ 和 $w_i$（$1 \le c_i \le 200$，$1 \le w_i \le 10^9$）—— 描述顶点 $i$ 上商人的卡牌信息。

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

下一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）—— 询问个数。

接下来的 $q$ 行中，每行包含两个整数 $p$ 和 $r$（$1 \le p \le n$，$1 \le r \le 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

---

样例 1 中的第三个询问解释

游戏过程如下：

1. 在顶点 $1$ 与商人交易，购买 $1$ 张威力值为 $9$ 的卡牌，花费 $3$ 枚硬币，剩余 $1$ 枚硬币。
2. 从顶点 $1$ 移动到顶点 $2$。
3. 从顶点 $2$ 移动到顶点 $3$。
4. 在顶点 $3$ 与商人交易，购买 $1$ 张威力值为 $2$ 的卡牌，花费 $1$ 枚硬币，剩余 $0$ 枚硬币。

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

---

样例 2 中的第五个询问解释

1. 从顶点 $1$ 移动到顶点 $3$。
2. 在顶点 $3$ 购买 $1$ 张威力值为 $2$ 的卡牌，花费 $1$ 枚硬币，剩余 $3$ 枚硬币。
3. 从顶点 $3$ 移动到顶点 $4$。
4. 在顶点 $4$ 购买 $1$ 张威力值为 $9$ 的卡牌，花费 $3$ 枚硬币，剩余 $0$ 枚硬币。

总威力值为 $2 + 9 = 11$。

---

样例 2 中的第六个询问解释

1. 从顶点 $1$ 移动到顶点 $2$。
2. 在顶点 $2$ 购买 $1$ 张威力值为 $5$ 的卡牌，花费 $2$ 枚硬币，剩余 $3$ 枚硬币。
3. 从顶点 $2$ 移动到顶点 $4$。
4. 在顶点 $4$ 购买 $1$ 张威力值为 $9$ 的卡牌，花费 $3$ 枚硬币，剩余 $0$ 枚硬币。

总威力值为 $5 + 9 = 14$。

---

样例 2 中的第七个询问解释

1. 在顶点 $1$ 购买 $10$ 张威力值为 $1000$ 的卡牌，花费 $10 \times 10 = 100$ 枚硬币，剩余 $1$ 枚硬币。
2. 从顶点 $1$ 移动到顶点 $3$。
3. 在顶点 $3$ 购买 $1$ 张威力值为 $2$ 的卡牌，花费 $1$ 枚硬币，剩余 $0$ 枚硬币。
4. 从顶点 $3$ 移动到顶点 $4$。

总威力值为 $10 \times 1000 + 2 = 10002$。