#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int maxn = 105;
int n, m, k;
vector<set<int>> mp(maxn);
vector<int> g, ans;
int vis[maxn], pre[maxn], pres[maxn][maxn*maxn];
ll dp[maxn][maxn*maxn];
P query[maxn];
int c = 0;
bool found(int u, int t){
    vis[u] = t;
    for(set<int>::iterator i = mp[u].begin(); i != mp[u].end(); i++){
        int v = *i;
        if(vis[v] == t)    continue;
        vis[v] = t;
        if(pre[v] == 0 || found(pre[v], t)){
            pre[v] = u;
            return true;
        }
    }
    return false;
}
int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		mp[u].insert(v+n);
	}
	for(int i = 1; i <= k; i++){
		scanf("%lld%lld", &query[i].first, &query[i].second);
	}
	for(int i = 1; i <= n; i++){
		if(found(i, i))	c++;	
	}
	for(int i = c; i >= 1; i--){
		if(i == 1)	
			int a = 1;
		int now;
		static vector<set<int>> _mp;
		_mp = mp;
		
		for(int j = 1; j <= n; j++){
			int cnt = 0;
			mp = _mp;
			mp[j].clear();
			if(i == 1 && j == 1){
				int a = 1;
			}
			for(int i = 1; i <= 2*n; i++)	vis[i] = pre[i] = 0;
			for(int k = 1; k <= n; k++){
				if(found(k, k))	cnt++;	
			}
			if(cnt < i)	now = j;
			mp = _mp, cnt = 0;
			for(int k = 1; k <= n; k++){
				mp[k].erase(j+n);
			}
			for(int i = 1; i <= 2*n; i++)	vis[i] = pre[n+i] = 0;
			for(int k = 1; k <= n; k++){
				if(found(k, k))	cnt++;	
			}
			if(cnt < i)	now = -j;
		}
		mp = _mp;
		if(now < 0){
			for(int k = 1; k <= n; k++){
				mp[k].erase(-now+n);
			}
		}else{
			mp[now].clear();
		}
		g.push_back(now);
	}
	reverse(g.begin(), g.end());
	for(int i = 0; i <= c; i++)	dp[0][i] = -1e9-7;
	dp[0][c] = 0;
	for(int i = 0; i < k; i++){
		for(int j = 0; j <= c; j++)	dp[i+1][j] = -1e9-7;
		for(int j = 0; j <= c; j++){
			if(dp[i][j] == -1e18-7)	continue;
			for(int h = 0; h <= j; h++){
				if(i + 1 + h >= n)	break;
				int t = j - h;
				ll add = max(0ll, query[i+1].first - t * query[i+1].second);
				if(dp[i+1][h] < dp[i][j] + add){
					dp[i+1][h] = dp[i][j] + add;
					pres[i+1][h] = j;
				}
			}
		}
	}
	int index = max_element(dp[k], dp[k]+c+1) - dp[k];
	for(int i = k; i >= 1; i--){
		int cnt = pres[i][index];
		ans.push_back(0);
		for(int j = index; j < cnt; j++){
			ans.push_back(g.back());	
			g.pop_back();	
		}
		index = cnt;
	}
	printf("%d\n", ans.size());
	for(int i = ans.size() - 1; i >= 0; i--){
		printf("%d ", ans[i]);
	}
	return 0;
}