Goblins And Gnomes
Contest: Educational Codeforces Round 109 (Rated for Div. 2)
Difficulty rating: 2800
Tags: brute force, dp, flows, graph matchings

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!

Input format:
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.

Output format:
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 > 0$$$ then Monocarp blocks all tunnels going out from the hall $$$b_i$$$;
- if $$$b_i < 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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
5 4 4
1 2
2 3
4 3
5 3
100 1
200 5
10 10
100 1

Example output:
6
-2 -3 0 0 0 0

Example input:
5 4 4
1 2
2 3
4 3
5 3
100 100
200 5
10 10
100 1

Example output:
6
0 -3 0 0 1 0

Editorial:
First of all, let's try to solve the following problem: given a DAG, cover its vertices with the minimum number of vertex-disjoint paths. Solving this problem allows us to calculate the number of goblins that can pillage all of the halls when the tunnel network is fixed. This problem is a fairly classical one; since the number of vertices in each path is greater than the number of arcs in it exactly by $$$1$$$, we should take the maximum possible number of arcs into our paths. So we can reduce this problem to bipartite maximum matching — build a bipartite graph where each part consists of $$$n$$$ vertices, and for every directed arc $$$(x, y)$$$ in the original graph, connect the vertex $$$x$$$ of the left part to the vertex $$$y$$$ in the right part of the bipartite graph. The maximum matching in this graph allows us to pick the maximum number of arcs into the paths of the original problem (the matching ensures that each vertex has at most one chosen ingoing arc and at most one chosen outgoing arc, so the paths are vertex-disjoint). Okay, now we at least can check if the goblin wave can pillage all of the halls.
Let's say that the minimum number of goblins required to pillage the original city is $$$c$$$. Obviously, in order to pass the $$$c$$$-th wave and waves after it, we have to increase this number. In one minute, Monocarp can block all of the tunnels leading to some hall or out of some hall — and in terms of our reduction to the bipartite matching problem, it means that we remove all edges connected to some vertex of the bipartite graph. Obviously, in one minute, we can increase $$$c$$$ by at most $$$1$$$, since $$$c$$$ is equal to the difference between $$$n$$$ and the maximum matching size.
It turns out that it's always possible to choose a vertex that belongs to all maximum matchings in the bipartite graph (note that it doesn't work in non-bipartite graphs, but in our problem, it doesn't matter). For the proof of this fact, you can check the last paragraph of the editorial. So, each minute Monocarp prepares for a wave, he increases the maximum number of goblins he can repel by $$$1$$$.
Now the solution splits into two much easier parts. The first part is finding a sequence in which Monocarp blocks the tunnels, so that each his action reduces the size of the maximum matching by $$$1$$$. Since the constraints are small, even a naive approach in $$$O(n^5)$$$ — always iterate on the vertex we try to remove from the graph and check that removing it is possible by running Kuhn's algorithm — is fast enough. The second part is to choose when Monocarp calls waves of goblins and when he prepares for them — this can be easily done with dynamic programming: let $$$dp_{i,j}$$$ be the maximum Monocarp's score if he has already passed $$$i$$$ waves, and the current size of the maximum matching is $$$j$$$. The most naive implementation of this dynamic programming runs in $$$O(n^3)$$$, so the whole solution works in $$$O(n^5)$$$.
We can improve it to $$$O(n^3)$$$, though it is not needed under these constraints. Instead of finding the vertices to remove from the bipartite graph one-by-one, let's find all of them at once in $$$O(n^3)$$$. Recall that the size of maximum matching in a bipartite graph is equal to the size of its minimum vertex cover, and the minimum vertex cover can be reconstructed after finding the maximum matching. If we remove a vertex from the minimum vertex cover, the size of the minimum vertex cover of the remaining graph is reduced by $$$1$$$, so the size of the maximum matching is reduced by $$$1$$$ as well. It means that we can always choose to remove a vertex from the minimum vertex cover we found. By the way, it also proves that it's always possible to remove a vertex from a bipartite graph so the size of the maximum matching decreases by $$$1$$$ (obviously, if it's not $$$0$$$ already).