#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);};
}

#define int long long

const int N=55;
int v[N],n,m,k,f[N][N],F[N][N],match[N];
bool L[N],R[N],bematched[N];
vector<int> g[N],vec,ans;

bool dfs(int x,int tg){
	if(v[x]==tg) return 0;
	v[x]=tg;
	for(int y:g[x]) if(!match[y]||dfs(match[y],tg)) return match[y]=x,1;
	return 0;
}

void dfs(int x){
	if(L[x]) return ;
	L[x]=1;
	for(int y:g[x]) if(!R[y]&&match[y]) R[y]=1,dfs(match[y]);
}

signed main(){
	read(n);read(m);read(k);
	for(int i=1,x,y;i<=m;i++){
		read(x);read(y);
		g[x].push_back(y);
	}
	int cnt=0;
	for(int i=1;i<=n;i++) cnt+=dfs(i,i);
	for(int i=1;i<=n;i++) bematched[match[i]]=1;
	for(int i=1;i<=n;i++) if(!bematched[i]) dfs(i);
	for(int i=1;i<=n;i++) if(!L[i]) vec.push_back(i);
	for(int i=1;i<=n;i++) if(R[i]) vec.push_back(-i);
	for(int i=0;i<=k;i++) for(int j=0;j<=n;j++) f[i][j]=-1e15;
	f[0][cnt]=0;
	for(int i=1,x,y;i<=k;i++){
		read(x);read(y);
		for(int j=0;j<n-i;j++){
			for(int o=j;o<=cnt;o++){
				int w=f[i-1][o]+max(0ll,x-y*(o-j));
				if(w>f[i][j]) f[i][j]=w,F[i][j]=o-j;
			}
		}
	}
	int mx=-1e15,po=-1;
	for(int i=0;i<=n;i++) if(f[k][i]>mx) mx=f[k][i],po=i;
	for(int i=k;i;i--){
		ans.push_back(0);
		for(int j=1;j<=F[i][po];j++) ans.push_back(vec.back()),vec.pop_back();
		po+=F[i][po];
	}
	write(ans.size());puts("");
	reverse(ans.begin(),ans.end());
	for(int x:ans) write(x),putchar(' ');
}