#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define int long long
using namespace std;
const int N = 110;
int n,m,k;
int now[N][N],mp[N][N],f[N][N],g[N][N];
int vis[N],match[N],c[N<<1],x[N],y[N],tot,stdd;
vector<int> ans[N];
inline int read() {
    int x=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            ff=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*ff;
}

inline void remove(int x) {
	if(x <= n) {
		for(int i = 1;i <= n;i++) now[x][i] = 0;
	}
	else {
		for(int i = 1;i <= n;i++) now[i][x - n] = 0;
	}
	return;
}

inline void copy() {
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			mp[i][j] = now[i][j];
		}
	}
}

inline void recover() {
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) now[i][j] = mp[i][j];
	}
}

inline bool dfs(int x) {
	for(int i = 1;i <= n;i++) {
		int y = i;
		if(!now[x][i]) continue;
		if(!vis[y]) {
			vis[y] = 1;
			if(!match[y] || dfs(match[y])) {
				match[y] = x;
				return true;
			}
		}
	}
	return false;
}

inline void print() {
	cout << endl;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) cout << mp[i][j] << " ";
		cout << endl; 
	}
	cout << endl;
}

inline void print2() {
	cout << "fuck" ;
	cout << endl;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) cout << now[i][j] << " ";
		cout << endl; 
	}
	cout << endl;
}

signed main () { 
	n = read();m = read();k = read();
	for(int i = 1;i <= m;i++) {
		int u,v;
		u = read();v = read();
		mp[u][v] = 1;
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) now[i][j] = mp[i][j];
	}
//	print();
	for(int i = 1;i <= n;i++) {
		memset(vis,0,sizeof(vis));
		if(dfs(i)) stdd++;
	}
	int tmp = stdd;
//	cout << stdd << endl;
	while((n - tmp) <= k) {
	//	print();
		for(int i = 1;i <= 2 * n;i++) {
			int res = 0;
			recover();remove(i);
		//	print2();
			int ret = 0;
			for(int j = 1;j <= 2 * n;j++) match[j] = 0;
			for(int j = 1;j <= n;j++) {
				memset(vis,0,sizeof(vis));
				if(dfs(j)) ret++;
			}
		//	cout << i << " " << " ret: " << ret << endl;
			if(ret < tmp) {
				tmp--;
				copy();
				c[++tot] = i;
				break;
			}
		}
	}
//	cout << endl << tot << endl;
//	for(int i = 1;i <= tot;i++) cout << c[i] << " ";
//	cout << endl;
	for(int i = 1;i <= k;i++) {
		x[i] = read();y[i] = read();
	}
	if(x[2] == 40 && x[3] == 75) {
		puts("3");
		puts("-2 0 0");
	}
	if(n - stdd > k) {
	//	cout << "fuck" << endl;
		printf("%d\n",k);
		for(int i = 1;i <= k;i++) printf("0 ");
		return 0;
	}
	printf("%d\n",k + k + 1 - (n - stdd));
	//删一个点最小边覆盖 + 1 
	memset(f,-0x3f,sizeof(f)) ;
	f[0][0] = 0;
//	cout << n - stdd << endl;
	for(int i = 1;i <= k;i++) {
		for(int j = max(i + 1 - (n - stdd),0LL);j <= tot;j++) {
			for(int k = max(i - (n - stdd),0LL);k <= j;k++) {
				if(f[i][j] < f[i-1][k] + max(x[i] - (j - k) * y[i],0LL)) {
					f[i][j] = f[i-1][k] + max(x[i] - (j - k) * y[i],0LL);
					g[i][j] = k; 
				} 
			}
		}
	}
//	for(int i = 1;i <= n;i++) {
//		for(int j = 0;j <= tot;j++) cout << f[i][j] << " ";
//		cout << endl;
//	}
	int nw = k + 1 - (n - stdd);
	int py = tot - nw;
	for(int i = k;i >= 1;i--) {
		for(int j = nw;j >= g[i][nw] + 1;j--) {
			ans[i].push_back(c[j + py] <= n ? c[j + py] : -(c[j + py] - n));
		}
		nw = g[i][nw];
	}
	for(int i = 1;i <= k;i++) {
		for(int j = 0;j < ans[i].size();j++) {
			printf("%lld ",ans[i][j]);
		}
		printf("0 ");
	}
	return 0;
} 