CF2115E.Gellyfish and Mayflower

Mayflower by Plum

May, Gellyfish's friend, loves playing a game called "Inscryption" which is played on a directed acyclic graph with $n$ vertices and $m$ edges. All edges $ a \rightarrow b$ satisfy $a \lt b$.

You start in vertex $1$ with some coins. You need to move from vertex $1$ to the vertex where the boss is located along the directed edges, and then fight with the final boss.

Each of the $n$ vertices of the graph contains a Trader who will sell you a card with power $w_i$ for $c_i$ coins. You can buy as many cards as you want from each Trader. However, you can only trade with the trader on the $i$-th vertex if you are currently on the $i$-th vertex.

In order to defeat the boss, you want the sum of the power of your cards to be as large as possible.

You will have to answer the following $q$ queries:

• Given integers $p$ and $r$. If the final boss is located at vertex $p$, and you have $r$ coins in the beginning, what is the maximum sum of the power of your cards when you fight the final boss? Note that you are allowed to trade cards on vertex $p$.

《五月花》——Plum

五月（May）是水母（Gellyfish）的朋友，她热衷于玩一款名为“Inscryption”的游戏。该游戏在一个具有 $n$ 个顶点和 $m$ 条边的有向无环图（DAG）上进行，且所有边 $ a \rightarrow b$ 均满足 $a \lt b$。

你从顶点 $1$ 出发，携带若干枚金币。你需要沿着有向边从顶点 $1$ 移动至最终 Boss 所在的顶点，然后与 Boss 战斗。

图中每个顶点 $i$ 上均有一位商人，可向你出售一张力量值为 $w_i$、售价为 $c_i$ 枚金币的卡牌。你可从每位商人处购买任意数量的卡牌。但仅当你恰好位于顶点 $i$ 时，才可与该顶点上的商人交易。

为击败 Boss，你希望所持卡牌的总力量值尽可能大。

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

• 给定整数 $p$ 和 $r$。若最终 Boss 位于顶点 $p$，且你初始拥有 $r$ 枚金币，则你在与 Boss 战斗时所能达到的最大卡牌总力量值是多少？注意：你可以在顶点 $p$ 处与商人交易。

The first line of input contains two integers $n$ and $m$ ($1 \leq n \leq 200$, $n - 1 \leq m \leq \min(\frac {n(n-1)} 2, 2000)$) — the number of vertices and the number of edges.

The $i$-th of the following $n$ lines of input each contains two integers $c_i$ and $w_i$ ($1 \leq c_i \leq 200$, $1 \leq w_i \leq 10^9$) — describing the cards of the Trader on the $i$-th vertex.

In the following $m$ lines of input, each line contains two integers $u$ and $v$ ($1 \leq u \lt v \leq n$), indicating a directed edge from vertex $u$ to vertex $v$. It is guaranteed that every edge $(u,v)$ appears at most once.

The next line of input contains one single integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

In the following $q$ lines of input, each line contains two integers $p$ and $r$ ($1 \leq p \leq n$, $1 \leq r \leq 10^9$).

It is guaranteed that for all $i$, there exists a path from vertex $1$ to vertex $i$.

输入的第一行包含两个整数 $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$ 的路径。

For each query, output the answer to the query.

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

For the third query in the first example, we will play the game in the following order:

• buy $1$ card with $9$ power from the trader on vertex $1$, and you'll still have $1$ coin after the trade.
• move from vertex $1$ to vertex $2$.
• move from vertex $2$ to vertex $3$.
• buy $1$ card with $2$ power from the trader on vertex $3$, and you'll have no coins after the trade.

In the end, we will have $1$ card with $9$ power and $1$ card with $2$, so the sum of the power of the cards is $9+2=11$.

For the fifth query in the second example, we will play the game in the following order:

• move from vertex $1$ to vertex $3$.
• buy $1$ card with $2$ power from the trader on vertex $3$, and you'll still have $3$ coins after the trade.
• move from vertex $3$ to vertex $4$.
• buy $1$ card with $9$ power from the trader on vertex $4$, and you'll have no coins after the trade.

In the end, we will have $1$ card with $2$ power and $1$ card with $9$, so the sum of the power of the cards is $2+9=11$.

For the sixth query in the second example, we will play the game in the following order:

• move from vertex $1$ to vertex $2$.
• buy $1$ card with $5$ power from the trader on vertex $2$, and you'll still have $3$ coins after the trade.
• move from vertex $2$ to vertex $4$.
• buy $1$ card with $9$ power from the trader on vertex $4$, and you'll have no coins after the trade.

In the end, we will have $1$ card with $5$ power and $1$ card with $9$, so the sum of the power of the cards is $5+9=14$.

For the seventh query in the second example, we will play the game in the following order:

• buy $10$ cards with $1000$ power from the trader on vertex $1$, and you'll still have $1$ coin after the trade.
• move from vertex $1$ to vertex $3$.
• buy $1$ card with $2$ power from the trader on vertex $3$, and you'll have no coins after the trade.
• move from vertex $3$ to vertex $4$.

In the end, we will have $10$ cards with $1000$ power and $1$ card with $2$ power, so the sum of the power of the cards is $10 \cdot 1000+2=10\,002$.

对于第一个样例中的第三次查询，我们将按以下顺序进行游戏：

• 在顶点 $1$ 的商人处购买 $1$ 张力量值为 $9$ 的卡牌，交易后还剩余 $1$ 枚金币。
• 从顶点 $1$ 移动到顶点 $2$。
• 从顶点 $2$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量值为 $2$ 的卡牌，交易后金币数为 $0$。

最终，我们将拥有 $1$ 张力量值为 $9$ 的卡牌和 $1$ 张力量值为 $2$ 的卡牌，因此卡牌力量值总和为 $9+2=11$。

对于第二个样例中的第五次查询，我们将按以下顺序进行游戏：

• 从顶点 $1$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量值为 $2$ 的卡牌，交易后还剩余 $3$ 枚金币。
• 从顶点 $3$ 移动到顶点 $4$。
• 在顶点 $4$ 的商人处购买 $1$ 张力量值为 $9$ 的卡牌，交易后金币数为 $0$。

最终，我们将拥有 $1$ 张力量值为 $2$ 的卡牌和 $1$ 张力量值为 $9$ 的卡牌，因此卡牌力量值总和为 $2+9=11$。

对于第二个样例中的第六次查询，我们将按以下顺序进行游戏：

• 从顶点 $1$ 移动到顶点 $2$。
• 在顶点 $2$ 的商人处购买 $1$ 张力量值为 $5$ 的卡牌，交易后还剩余 $3$ 枚金币。
• 从顶点 $2$ 移动到顶点 $4$。
• 在顶点 $4$ 的商人处购买 $1$ 张力量值为 $9$ 的卡牌，交易后金币数为 $0$。

最终，我们将拥有 $1$ 张力量值为 $5$ 的卡牌和 $1$ 张力量值为 $9$ 的卡牌，因此卡牌力量值总和为 $5+9=14$。

对于第二个样例中的第七次查询，我们将按以下顺序进行游戏：

• 在顶点 $1$ 的商人处购买 $10$ 张力量值为 $1000$ 的卡牌，交易后还剩余 $1$ 枚金币。
• 从顶点 $1$ 移动到顶点 $3$。
• 在顶点 $3$ 的商人处购买 $1$ 张力量值为 $2$ 的卡牌，交易后金币数为 $0$。
• 从顶点 $3$ 移动到顶点 $4$。

最终，我们将拥有 $10$ 张力量值为 $1000$ 的卡牌和 $1$ 张力量值为 $2$ 的卡牌，因此卡牌力量值总和为 $10 \cdot 1000+2=10\,002$。