CF1525F.Goblins And Gnomes

Monocarp plays a computer game called "Goblins and Gnomes". In this game, he manages a large underground city of gnomes and defends it from hordes of goblins.

The city consists of $n$ halls and $m$ one-directional tunnels connecting them. The structure of tunnels has the following property: if a goblin leaves any hall, he cannot return to that hall.

The city will be attacked by $k$ waves of goblins; during the $i$-th wave, $i$ goblins attack the city. Monocarp's goal is to pass all $k$ waves.

The $i$-th wave goes as follows: firstly, $i$ goblins appear in some halls of the city and pillage them; at most one goblin appears in each hall. Then, goblins start moving along the tunnels, pillaging all the halls in their path.

Goblins are very greedy and cunning, so they choose their paths so that no two goblins pass through the same hall. Among all possible attack plans, they choose a plan which allows them to pillage the maximum number of halls. After goblins are done pillaging, they leave the city.

If all halls are pillaged during the wave — Monocarp loses the game. Otherwise, the city is restored. If some hall is pillaged during a wave, goblins are still interested in pillaging it during the next waves.

Before each wave, Monocarp can spend some time preparing to it. Monocarp doesn't have any strict time limits on his preparations (he decides when to call each wave by himself), but the longer he prepares for a wave, the fewer points he gets for passing it. If Monocarp prepares for the $i$-th wave for $t_i$ minutes, then he gets $\max(0, x_i - t_i \cdot y_i)$ points for passing it (obviously, if he doesn't lose in the process).

While preparing for a wave, Monocarp can block tunnels. He can spend one minute to either block all tunnels leading from some hall or block all tunnels leading to some hall. If Monocarp blocks a tunnel while preparing for a wave, it stays blocked during the next waves as well.

Help Monocarp to defend against all $k$ waves of goblins and get the maximum possible amount of points!

Monocarp 正在玩一款名为《哥布林与地精》的电脑游戏。在该游戏中，他管理一座庞大的地下地精城市，并抵御一波波哥布林的进攻。

这座城市由 $n$ 个大厅和 $m$ 条单向隧道组成，这些隧道连接着各个大厅。隧道结构具有如下性质：若一个哥布林离开某个大厅，则它再也无法返回该大厅。

城市将遭受 $k$ 波哥布林的攻击；第 $i$ 波攻击中，恰好有 $i$ 个哥布林进攻城市。Monocarp 的目标是成功抵御全部 $k$ 波攻击。

第 $i$ 波攻击过程如下：首先，$i$ 个哥布林出现在城市的若干大厅中并洗劫这些大厅；每个大厅至多出现一个哥布林。随后，哥布林沿隧道移动，在其路径上洗劫所有经过的大厅。

哥布林极其贪婪且狡猾，因此它们会选择行进路径，使得任意两个哥布林不会经过同一个大厅。在所有可能的进攻方案中，它们会选择能洗劫最多数量大厅的方案。哥布林完成洗劫后即离开城市。

若某一波攻击中所有大厅均被洗劫——Monocarp 游戏失败。否则，城市将被修复复原。若某个大厅在某波攻击中被洗劫，哥布林在后续波次中仍会试图再次洗劫该大厅。

在每波攻击开始前，Monocarp 可花费一定时间进行准备。Monocarp 对准备时间并无严格限制（他自行决定何时发起每一波攻击），但为第 $i$ 波攻击准备的时间越长，他通过该波所获得的分数就越少。若 Monocarp 为第 $i$ 波攻击准备了 $t_i$ 分钟，则他通过该波可获得 $\max(0, x_i - t_i \cdot y_i)$ 分（显然，若他在该过程中失败，则不得分）。

在为某波攻击做准备时，Monocarp 可以封堵隧道。他每花费一分钟，可选择以下两种操作之一：封堵从某一特定大厅出发的所有隧道，或封堵通向某一特定大厅的所有隧道。Monocarp 在为某波攻击准备时所封堵的隧道，在后续各波攻击中将持续保持封堵状态。

请帮助 Monocarp 抵御全部 $k$ 波哥布林进攻，并获取尽可能高的总分！

The first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 50$; $0 \le m \le \frac{n(n - 1)}{2}$; $1 \le k \le n - 1$) — the number of halls in the city, the number of tunnels and the number of goblin waves, correspondely.

Next $m$ lines describe tunnels. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). It means that the tunnel goes from hall $u_i$ to hall $v_i$. The structure of tunnels has the following property: if a goblin leaves any hall, he cannot return to that hall. There is at most one tunnel between each pair of halls.

Next $k$ lines describe the scoring system. The $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le 10^9$; $1 \le y_i \le 10^9$). If Monocarp prepares for the $i$-th wave for $t_i$ minutes, then he gets $\max(0, x_i - t_i \cdot y_i)$ points for passing it.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 50$；$0 \le m \le \frac{n(n - 1)}{2}$；$1 \le k \le n - 1$），分别表示城市中大厅的数量、隧道的数量以及哥布林波次的数量。

接下来的 $m$ 行描述隧道。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \ne v_i$），表示存在一条从大厅 $u_i$ 通往大厅 $v_i$ 的隧道。隧道结构具有如下性质：若一个哥布林离开任意一个大厅，则无法再返回该大厅。任意两个大厅之间至多存在一条隧道。

接下来的 $k$ 行描述计分系统。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le 10^9$；$1 \le y_i \le 10^9$）。若 Monocarp 为第 $i$ 波次准备了 $t_i$ 分钟，则他通过该波次可获得 $\max(0, x_i - t_i \cdot y_i)$ 分。

Print the optimal Monocarp's strategy in the following format:

At first, print one integer $a$ ($k \le a \le 2n + k$) — the number of actions Monocarp will perform. Next, print actions themselves in the order Monocarp performs them. The $i$-th action is described by a single integer $b_i$ ($-n \le b_i \le n$) using the following format:

• if $b_i \gt 0$ then Monocarp blocks all tunnels going out from the hall $b_i$;
• if $b_i \lt 0$ then Monocarp blocks all tunnels going into the hall $|b_i|$;
• if $b_i = 0$ then Monocarp calls the next goblin wave.

You can't repeat the same block action $b_i$ several times. Monocarp must survive all waves he calls (goblins shouldn't be able to pillage all halls). Monocarp should call exactly $k$ waves and earn the maximum possible number of points in total.

If there are several optimal strategies — print any of them.

按以下格式输出 Monocarp 的最优策略：

首先，输出一个整数 $a$（满足 $k \le a \le 2n + k$），表示 Monocarp 将执行的操作总数。接着，按 Monocarp 执行的顺序输出这些操作。第 $i$ 个操作由一个整数 $b_i$（满足 $-n \le b_i \le n$）描述，其含义如下：

• 若 $b_i > 0$，则 Monocarp 封锁所有从大厅 $b_i$ 出发的隧道；
• 若 $b_i < 0$，则 Monocarp 封锁所有通向大厅 $|b_i|$ 的隧道；
• 若 $b_i = 0$，则 Monocarp 召唤下一波哥布林。

不允许重复执行相同的操作 $b_i$。Monocarp 必须在所有他召唤的波次中存活（即哥布林不能洗劫全部大厅）。Monocarp 必须恰好召唤 $k$ 波哥布林，并使得最终获得的总分数尽可能高。

若存在多种最优策略，输出任意一种即可。

In the first example, Monocarp, firstly, block all tunnels going in hall $2$, secondly — all tunnels going in hall $3$, and after that calls all waves. He spent two minutes to prepare to wave $1$, so he gets $98$ points for it. He didn't prepare after that, that's why he gets maximum scores for each of next waves ($200$, $10$ and $100$). In total, Monocarp earns $408$ points.

In the second example, Monocarp calls for the first wave immediately and gets $100$ points. Before the second wave he blocks all tunnels going in hall $3$. He spent one minute preparing to the wave, so he gets $195$ points. Monocarp didn't prepare for the third wave, so he gets $10$ points by surviving it. Before the fourth wave he blocks all tunnels going out from hall $1$. He spent one minute, so he gets $99$ points for the fourth wave. In total, Monocarp earns $404$ points.

In the third example, it doesn't matter how many minutes Monocarp will spend before the wave, since he won't get any points for it. That's why he decides to block all tunnels in the city, spending $5$ minutes. He survived the wave though without getting any points.

在第一个例子中，Monocarp 首先封锁所有通向大厅 $2$ 的隧道，其次封锁所有通向大厅 $3$ 的隧道，然后召唤所有波次。他花费了两分钟为第 $1$ 波做准备，因此获得 $98$ 分；此后他未再进行任何准备，因此后续各波（第 $2$、$3$、$4$ 波）均获得满分（分别为 $200$、$10$ 和 $100$ 分）。总计，Monocarp 获得 $408$ 分。

在第二个例子中，Monocarp 立即召唤第 $1$ 波，获得 $100$ 分；在第 $2$ 波前，他封锁了所有通向大厅 $3$ 的隧道，花费了一分钟准备时间，因此获得 $195$ 分；Monocarp 未为第 $3$ 波做任何准备，仅靠存活获得 $10$ 分；在第 $4$ 波前，他封锁了所有从大厅 $1$ 出发的隧道，花费了一分钟，因此第 $4$ 波获得 $99$ 分。总计，Monocarp 获得 $404$ 分。

在第三个例子中，无论 Monocarp 在该波前花费多少分钟准备，他都无法获得任何分数。因此他决定封锁全城所有隧道，耗时 $5$ 分钟；尽管他成功存活了该波，但未获得任何分数。