#include<bits/stdc++.h>
#define N 1010
#define M 200010
#define ll long long
using namespace std;
inline int read(){
	static int x=0,f=1;x=0,f=1;
	static char ch=getchar();
	while(ch<'0'||ch>'9'){(ch=='-')?f*=-1:f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+int(ch-48),ch=getchar();
	return x*f;
}
vector<int>v[N];
int use[N],n,m;
namespace MCMF{
	int tot=1,head[M],dep[M];
	struct edge{
		int to,next,len;
	}dat[M];
	void add_edge(int x,int y,int z){
		dat[++tot]=(edge){y,head[x],z};
		head[x]=tot;
	}
	void Add_edge(int x,int y,int z){
		add_edge(x,y,z);
		add_edge(y,x,0);
	}
	int fuck[M],S,T;
	queue<int>q;
	int bfs(){
		for(int i=S;i<=T;i++)dep[i]=0,fuck[i]=head[i];
		dep[S]=1;
		q.push(S);
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=dat[i].next){
				int t=dat[i].to;
				if(!dat[i].len||dep[t])continue;
				dep[t]=dep[x]+1;
				q.push(t);
			}
		}
		return dep[T];
	}
	int dfs(int x,int limit){
		if(x==T)return limit;
		int sum=0;
		for(int i=fuck[x];i;i=dat[i].next){
			fuck[x]=i;
			int t=dat[i].to;
			if(!dat[i].len||dep[t]!=dep[x]+1)continue;
			int hh=dfs(t,min(limit,dat[i].len));
			dat[i].len-=hh;
			dat[i^1].len+=hh;
			sum+=hh;
			limit-=hh;
			if(!limit)return sum;
		}
		return sum;
	}
	int dinic(){
		int sum=0;
		while(bfs()){
			sum+=dfs(S,1e9);
		}
		return sum;
	}
	void init(int _S,int _T){
		S=_S,T=_T;
		for(int i=S;i<=T;i++)head[i]=0;
		tot=1;
		for(int i=S;i<=T;i++){
			if(!use[i])for(int j=0;j<(int)v[i].size();j++)if(!use[v[i][j]])Add_edge(i,v[i][j],1);
		}
	}
}
using namespace MCMF;
int last[N][N],k,ans[N],cnt,a[N];
ll dp[N][N];
int main(){
	cin>>n>>m>>k;
	int S=0,T=2*n+1;
	for(int i=1;i<=n;i++)v[S].push_back(i);
	for(int i=n+1;i<=2*n;i++)v[i].push_back(T);
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		v[x].push_back(y+n);
	}
	init(S,T);
	int res=dinic();
	int maxx=res;
	while(res){
		for(int i=1;i<=2*n;i++){
			if(use[i])continue;
			use[i]=1;
			init(S,T);
			if(dinic()==res-1){
				ans[++cnt]=i;
				break;
			}
			use[i]=0;
		}
		res--;
	}
	memset(dp,-63,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=k;i++){
		ll x=read(),y=read();
		for(int j=max(i-(n-maxx)+1,0);j<=cnt;j++){
			for(int w=0;w<=j;w++){
				if(dp[i][j]<dp[i-1][w]+max(0ll,x-y*(j-w))){
					dp[i][j]=dp[i-1][w]+max(0ll,x-y*(j-w));
					last[i][j]=w;
				}
			}
		}
	}
	int now=0;
	for(int i=0;i<=cnt;i++)if(dp[k][i]>dp[k][now])now=i;
	cout<<now+k<<endl;
	for(int i=k;i>=1;i--){
		a[i]=now-last[i][now];
		now=last[i][now];
	}
	now=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=a[i];j++)now++,printf("%d ",(ans[now]>n)?-(ans[now]-n):ans[now]);
		printf("%d ",0);
	}
}