#include<bits/stdc++.h> 
using namespace std;
const int M = 2005;
const int inf = 0x3f3f3f3f;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,t,mx,a[M],b[M],d[M],del[M];
int tot,S,T,f[M],dis[M],dp[55][55],pre[55][55];
struct edge
{
	int v,c,next;
}e[2*M];
void add(int u,int v,int c)
{
	e[++tot]=edge{v,c,f[u]},f[u]=tot;
	e[++tot]=edge{u,0,f[v]},f[v]=tot;
}
int bfs()
{
	for(int i=S;i<=T;i++) dis[i]=0;
	queue<int> q;
	q.push(S);dis[S]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();
		if(u==T) return 1;
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v;
			if(e[i].c>0 && !dis[v])
			{
				dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
int dfs(int u,int ept)
{
	if(u==T) return ept;
	int flow=0,tmp=0;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(e[i].c>0 && dis[v]==dis[u]+1)
		{
			tmp=dfs(v,min(e[i].c,ept));
			if(!tmp) continue;
			ept-=tmp;
			e[i].c-=tmp;
			e[i^1].c+=tmp;
			flow+=tmp;
			if(!ept) break;
		}
	}
	return flow;
}
int get()
{
	S=0;T=2*n+1;tot=1;
	for(int i=S;i<=T;i++) f[i]=0;
	for(int i=1;i<=m;i++)
	{
		int u=a[i],v=b[i];
		add(u+n,v,1);//x is in / x+n is out;
	}
	for(int i=1;i<=n;i++)
    {
        if(!del[i+n]) add(S,i+n,1);
        if(!del[i]) add(i,T,1);
    }
	int res=0;
	while(bfs()) res+=dfs(S,inf);
	return res;
}
void print(int x,int y)
{
	if(!x) return ;
	print(x-1,pre[x][y]);
	for(int i=pre[x][y]+1;i<=y;i++)
	{
		if(d[i]>n) printf("%lld ",d[i]-n);
		else printf("%lld ",-d[i]);
	}
	printf("0 ");
}
signed main()
{
	n=read();m=read();k=read();
	for(int i=1;i<=m;i++)
		a[i]=read(),b[i]=read();
	mx=get();
	for(int i=1;i<=mx;i++)
		for(int j=1;j<=2*n;j++)
			if(!del[j])
			{
				del[j]=1;
				if(get()==mx-i)//we can delete j to reduce the maxmatch
				{
					d[++t]=j;
					break;
				}
				del[j]=0;
			}
	memset(dp,-0x3f,sizeof dp);
	dp[0][0]=0;
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read();
		for(int j=0;j<=t;j++)
		{
			if(i-j>=n-mx) continue;//illegal
			for(int k=0;k<=j;k++)//we choose k now
				if(dp[i][j]<dp[i-1][j-k]+max(0ll,x-k*y))
				{
					dp[i][j]=dp[i-1][j-k]+max(0ll,x-k*y);
					pre[i][j]=j-k;
				}
		}
	}
	int p=0;
	for(int i=0;i<=t;i++)
		if(dp[k][i]>dp[k][p])
			p=i;
	printf("%lld\n",k+p);
	print(k,p);
}