套路地，将 DAG 的最小不交路径覆盖转化为点数减去拆点以后最大匹配。感性理解就是一开始每个点都是一条路径，一个匹配意味着两条路径结合了。
由题意知，第 \(i\) 次进攻时最小不交路径覆盖必须 \(> i\)，也就是说，设最大匹配为 \(k\)，那么 \(n - k > i\)，即 \(k \le n - i - 1\)。
同时，通过上面的转化，题中删除某个点所有入边或出边的操作也可以转化为，在二分图上删去一个点，左右都可以。
我们发现，只要 \(k > 0\)，我们总能找到一个点，使得删掉后 \(k \gets k - 1\)。因为由 Konig 定理得二分图最大匹配 \(=\) 最小点覆盖，只要从最小点覆盖中随意删除一个点即可。
于是我们可以求出一个删点序列，满足依次删除序列中的点，\(k\) 都能依次减 \(1\)。
既然我们已经能够满足任意次删点了，那我们就可以对着每次进攻的参数 \(a_i, b_i\) 做一个 dp，求出最大收益。输出方案就直接依次输出上面求出的删点序列即可。
时间复杂度大概是 \(O(n^5)\)？
code
// Problem: F. Goblins And Gnomes
// Contest: Codeforces - Educational Codeforces Round 109 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1525/F
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 110;
const int maxm = 10000;
const int inf = 0x3f3f3f3f;
int n, m, K, a[maxn], id[maxn][2], ntot, S, T, head[maxn], len, di[maxn];
ll f[maxn][maxn], g[maxn][maxn];
bool vis[maxn];
pii E[maxm];
struct edge {
int to, next, cap, flow;
} edges[maxm];
inline void add_edge(int u, int v, int c, int f) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
head[u] = len;
}
struct Dinic {
int d[maxn], cur[maxn];
bool vis[maxn];
inline void add(int u, int v, int c) {
add_edge(u, v, c, 0);
add_edge(v, u, 0, 0);
}
inline bool bfs() {
for (int i = 1; i <= ntot; ++i) {
vis[i] = 0;
d[i] = -1;
}
queue<int> q;
q.push(S);
d[S] = 0;
vis[S] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int u, int a) {
if (u == T || !a) {
return a;
}
int flow = 0, f;
for (int &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline int solve() {
int flow = 0;
while (bfs()) {
for (int i = 1; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
inline int work() {
len = 1;
mems(head, 0);
for (int i = 1; i <= n; ++i) {
if (!vis[id[i][0]]) {
solver.add(S, id[i][0], 1);
}
if (!vis[id[i][1]]) {
solver.add(id[i][1], T, 1);
}
}
for (int i = 1; i <= m; ++i) {
int u = E[i].fst, v = E[i].scd;
if (!vis[id[u][0]] && !vis[id[v][1]]) {
solver.add(id[u][0], id[v][1], 1);
}
}
return solver.solve();
}
void solve() {
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &E[i].fst, &E[i].scd);
}
for (int i = 1; i <= n; ++i) {
id[i][0] = ++ntot;
di[ntot] = i;
id[i][1] = ++ntot;
di[ntot] = -i;
}
S = ++ntot;
T = ++ntot;
int flow = work();
for (int i = 1; i <= flow; ++i) {
for (int j = 1; j <= n * 2; ++j) {
if (!vis[j]) {
vis[j] = 1;
if (work() == flow - i) {
a[i] = j;
break;
}
vis[j] = 0;
}
}
}
mems(f, -0x3f);
f[0][0] = 0;
for (int i = 1; i <= K; ++i) {
ll x, y;
scanf("%lld%lld", &x, &y);
for (int j = 0; j <= flow; ++j) {
if (n - (flow - j) <= i) {
continue;
}
for (int k = 0; k <= j; ++k) {
if (f[i][j] < f[i - 1][k] + max(0LL, x - y * (j - k))) {
f[i][j] = f[i - 1][k] + max(0LL, x - y * (j - k));
g[i][j] = k;
}
}
}
}
vector<int> ans;
ll p = 0;
for (int i = 1; i <= flow; ++i) {
if (f[K][i] > f[K][p]) {
p = i;
}
}
for (int i = K, j = p; i; j = g[i--][j]) {
ans.pb(0);
for (int k = j; k > g[i][j]; --k) {
ans.pb(di[a[k]]);
}
}
reverse(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int x : ans) {
printf("%d ", x);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}