#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;
const int MAXN=55;
const ll INF=1e18;

#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define fi first
#define se second
template<typename T> void chkmax(T& x,T y){if(y>x)x=y;}
template<typename T> void chkmin(T& x,T y){if(y<x)x=y;}

int N,M,K,x[MAXN],y[MAXN];bool G[MAXN][MAXN],tG[MAXN][MAXN];
int arr[MAXN],chs[MAXN],len;

int link[MAXN];bool vis[MAXN];
int dfs(int u){
	for(int i=1;i<=N;++i)if(G[u][i]&&!vis[i]){
		vis[i]=1;
		if(!link[i]||dfs(link[i])){link[i]=u;return 1;}
	}
	return 0;
}
int qry(){
	int ret=N;
	for(int i=1;i<=N;++i)link[i]=0;
	for(int i=1;i<=N;++i){
		for(int j=1;j<=N;++j)vis[j]=0;
		if(dfs(i))--ret;
		//for(int j=1;j<=N;++j)printf("%d ",link[j]);putchar('\n');
	}
	return ret;
}

ll dp[MAXN][MAXN];int pre[MAXN][MAXN],stk[MAXN],slen;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("p1.in","r",stdin);
	freopen("p1.out","w",stdout);
	#endif
	scanf("%d%d%d",&N,&M,&K);int u,v;
	for(int i=1;i<=M;++i)scanf("%d%d",&u,&v),G[u][v]=1;
	for(int i=1;i<=N;++i)scanf("%d%d",&x[i],&y[i]);
	/*for(int i=1;i<=N;++i){
		for(int j=1;j<=N;++j)printf("%d ",G[i][j]);
		putchar('\n');
	}*/
	arr[0]=qry();
	//printf("arr[0]=%d\n",arr[0]);
	for(len=1;arr[len-1]<N;++len){
		int mx=0,mxi;
		for(int i=1;i<=N;++i){
			for(int j=1;j<=N;++j)tG[i][j]=G[i][j],G[i][j]=0;
			if(qry()>mx)mx=qry(),mxi=i;
			for(int j=1;j<=N;++j)G[i][j]=tG[i][j];
			for(int j=1;j<=N;++j)tG[j][i]=G[j][i],G[j][i]=0;
			if(qry()>mx)mx=qry(),mxi=-i;
			for(int j=1;j<=N;++j)G[j][i]=tG[j][i];
		}
		arr[len]=mx;
		if(mxi>0){
			for(int i=1;i<=N;++i)G[mxi][i]=0;
		}else{
			for(int i=1;i<=N;++i)G[i][-mxi]=0;
		}
		chs[len]=mxi;
	}--len;
	//printf("arr:");for(int i=0;i<=len;++i)printf("%d ",arr[i]);putchar('\n');
	//printf("chs:");for(int i=0;i<=len;++i)printf("%d ",chs[i]);putchar('\n');
	dp[0][0]=0;
	for(int i=1;i<=len;++i)dp[0][i]=-INF;
	for(int i=1;i<=K;++i){
		for(int j=0;j<=len;++j){
			if(arr[j]<=i)dp[i][j]=-INF;
			else{
				dp[i][j]=-INF;
				for(int k=0;k<=j;++k){
					ll tmp=dp[i-1][k]+max(0ll,x[i]-1ll*y[i]*(j-k));
					if(tmp>dp[i][j]){
						dp[i][j]=tmp;
						pre[i][j]=j-k;
					}
				}
			}
		}
	}
	ll ans=-INF;int ansi;
	for(int i=0;i<=len;++i)if(dp[K][i]>ans)ans=dp[K][i],ansi=i;
	for(int i=K;i>=1;--i){
		stk[++slen]=0;
		for(int j=1;j<=pre[i][ansi];++j)stk[++slen]=chs[ansi-j+1];
		ansi-=pre[i][ansi];
		//printf("i=%d,ansi=%d\n",i,ansi);
	}
	//printf("ans=%lld\n",ans);
	printf("%d\n",slen);
	while(slen)printf("%d ",stk[slen--]);
	return 0;
}