#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;

template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl='\n';
const int mxN=101; 
const int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;


// Black Box Dinic from KACTL (use CP-ALGO one if I want to understand)
struct Dinic {
    struct Edge {
        int to, rev;
        ll c, oc;
        ll flow() { return max(oc - c, 0LL); } // if you need flows
    };
    vi lvl, ptr, q;
    vector<vector<Edge>> adj;
    Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
    void addEdge(int a, int b, ll c, ll rcap = 0) {
        adj[a].push_back({b, siz(adj[b]), c, c});
        adj[b].push_back({a, siz(adj[a]) - 1, rcap, rcap});
    }
    ll dfs(int v, int t, ll f) {
        if (v == t || !f) return f;
        for (int& i = ptr[v]; i < siz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1)
                if (ll p = dfs(e.to, t, min(f, e.c))) {
                    e.c -= p, adj[e.to][e.rev].c += p;
                    return p;
                }
        }
        return 0;
    }
    ll calc(int s, int t) {
        ll flow = 0; q[0] = s;
        FOR(L,0,31) do { // 'int L=30' maybe faster for random data
            lvl = ptr = vi(siz(q));
            int qi = 0, qe = lvl[s] = 1;
            while (qi < qe && !lvl[t]) {
                int v = q[qi++];
                for (Edge e : adj[v])
                    if (!lvl[e.to] && e.c >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
            }
            while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
        } while (lvl[t]);
        return flow;
    }
    bool leftOfMinCut(int a) { return lvl[a] != 0; }
};

int n, m, k;
vector<ar<int, 2>> v;
vpii e;

ll dp[mxN][mxN]; // MIN COST TO REMOVE X VERTICES WHILE MAINTAINING FIRST Y NODES AS BEING CORRECT  
pii lst[mxN][mxN];
vi ord;

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    Dinic dd(n*2+2); 
    FOR(i, 1, n+1) dd.addEdge(0, i, 1); 
    FOR(i, n+1, 2*n+1) dd.addEdge(i, 2*n+1, 1); 
    F0R(i, m){
        int e1, e2; cin >> e1 >> e2; 
        e.pb({e1, e2+n}); 
        dd.addEdge(e1, e2+n, 1); 
    }
    int tot=dd.calc(0, 2*n+1); int curFlow=tot;
    vi alive(2*n+2, 1); 
    while(curFlow>0){
        FOR(i, 1, n*2+1){
            if(alive[i]==0) continue;
            alive[i]=0;
            Dinic d(2*n+2); 
            FOR(i, 1, n+1) d.addEdge(0, i, 1); 
            FOR(i, n+1, 2*n+1) d.addEdge(i, 2*n+1, 1); 
                for(auto[u, v]:e){
                if(alive[u]&&alive[v]) d.addEdge(u, v, 1); 
            }
            int v=d.calc(0, 2*n+1);
            // cout << i << ' ' << curFlow << ' ' <<v << nl;
            if(v==curFlow-1) {
                // cout << i << nl;
                ord.pb(i); 
                curFlow--;
                break;
            }
            alive[i]=1;
        } 
    }
    F0R(i, n+1) F0R(j, n+1) dp[i][j]=-infLL;
    dp[0][n-tot]=0;
    // cout << tot << nl;
    FOR(i, 0, k){
        ll X, Y; cin >> X >> Y;
        FOR(j, i+1, n+1){
            F0R(k, n+1){
                if(ckmax(dp[i+1][j+k], dp[i][j]+max(X-Y*k, 0LL))){
                    lst[i+1][j+k]={i, j};
                }
            }
        }
        // FOR(j, i, n+1){
        //     cout << i << ' ' << j << ' '  << dp[i][j] << '\n'; 
        // }
    }
    // cout << dp[k][k+1] << nl;
    reverse(all(ord));
    int x=k, y=k+1; 
    vi psh;
    int cnt=0;
    while(x!=0){
        psh.pb(0); 
        auto[X, Y]=lst[x][y];
        // cout << X << ' ' << Y << ' ' << x << ' ' << y << "\n";
        FOR(i, Y, y) psh.pb(ord[cnt++]);
        x=X, y=Y; 
    }
    reverse(all(psh));

    cout << siz(psh) << '\n';
    for(auto v:psh){
        if(v<=n) cout << v;
        else cout << -(v-n);
        cout << ' ';
    }
    cout << '\n';
}
