/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const int maxn = 55, nil = 0, inf = 1e9;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n, m, k, uL[maxn], uR[maxn];
int pairV[maxn], pairU[maxn], dist[maxn];
long long dp[maxn][maxn], ff[maxn][maxn], x[maxn], y[maxn];
vector < int > g[maxn];
void read()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
    }
    for (int i = 1; i <= k; i ++)
        cin >> x[i] >> y[i];
}

vector < int > order;

bool bfs()
{
    queue < int > q;
    for (int i = 1; i <= n; i ++)
    {
        if (uL[i])
            continue;

        if (pairV[i] == nil)
        {
            dist[i] = 0;
            q.push(i);
        }
        else
            dist[i] = inf;
    }

    dist[nil] = inf;
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        if (dist[v] < dist[nil])
        {
            for (int i = 0; i < g[v].size(); i ++)
            {
                int u = g[v][i];
                if (uR[u])
                    continue;
                if (dist[pairU[u]] == inf)
                {
                    dist[pairU[u]] = dist[v] + 1;
                    q.push(pairU[u]);
                }
            }
        }
    }

    return (dist[nil] != inf);
}

bool dfs(int v)
{
    if (v == nil)
        return true;
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i];
        if (uR[u])
            continue;
        if (dist[pairU[u]] == dist[v] + 1 && dfs(pairU[u]))
        {
            pairV[v] = u;
            pairU[u] = v;
            return true;
        }
    }

    dist[v] = inf;
    return false;
}

int hopcroftKarp()
{
    for (int i = 1; i <= n; i ++)
        pairV[i] = nil;

    for (int i = 1; i <= n; i ++)
        pairU[i] = nil;

    int result = 0;
    while(bfs())
    {
        for (int i = 1; i <= n; i ++)
        {
            if (uL[i])
                continue;
            if (dfs(i))
                result ++;
        }
    }

    return result;
}

int mt[maxn], used[maxn];

bool try_kuhn(int v)
{
    if (used[v])
        return false;
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i];
        if (uR[u])
            continue;
        if (mt[u] == -1 || try_kuhn(mt[u]))
        {
            mt[u] = v;
            return true;
        }
    }
    return false;
}
int kuhn()
{
    memset(mt, -1, sizeof(mt));
    for (int i = 1; i <= n; i ++)
    {
        if (uL[i])
            continue;
        memset(used, 0, sizeof(used));
        try_kuhn(i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i ++)
        if (mt[i] != -1)
            cnt ++;

    return cnt;
}

int dd;
void find_order()
{

    int maxMatch = kuhn();

    dd = maxMatch;        int ver;
    while(n - maxMatch <= k)
    {
        bool done = false;

        for (int i = 1; i <= n && !done; i ++)
        {
            if (uL[i] == 1)
                continue;
            uL[i] = 1;
            int newMatch = kuhn();
            if (newMatch < maxMatch)
            {
                done = true;
                ver = i;
            }
            else
                uL[i] = 0;
        }

        for (int i = 1; i <= n && !done; i ++)
        {
            if (uR[i] == 1)
                continue;
            uR[i] = 1;
            int newMatch = kuhn();
            if (newMatch < maxMatch)
            {
                done = true;
                ver = -i;
            }
            else
                uR[i] = 0;
        }

        order.push_back(ver);
        maxMatch = kuhn();
    }

}

void solve_dp()
{
    int h = order.size();
    for (int i = 0; i <= k; i ++)
        for (int j = 0; j <= h; j ++)
            dp[i][j] = -1e18;
    for (int j = 0; j <= h; j ++)
    {
        if ((n - dd) + j <= 1)
            continue;
        dp[1][j] = max((ll)0, x[1] - j * y[1]);
    }

    for (int i = 2; i <= k; i ++)
    {

        for (int j = 0; j <= h; j ++)
        {
            if ((n - dd) + j <= i)
                continue;
            for (int p = 0; p <= j; p ++)
            {
                if (dp[i - 1][p] == -1e18)
                    continue;
                ll sum = dp[i - 1][p] + max((ll)0, x[i] - (j - p) * y[i]);
                if (sum > dp[i][j])
                {
                    dp[i][j] = sum;
                    ff[i][j] = p;
                }
            }
        }
    }


}

void print()
{
    stack < int > st;

    int i = k, j = order.size(), pl = order.size() - 1;
    while(i != 0)
    {
        st.push(0);
        int bef = ff[i][j];
        for (int p = 0; p < j - bef; p ++)
            st.push(order[pl --]);
        j = bef;
        i --;
    }

    cout << st.size() << endl;
    int bef = 0;
    while(!st.empty())
    {
        if (st.top() != bef || bef == 0)
        cout << st.top() << " ";
        bef = st.top();
        st.pop();
    }
}
void solve()
{
    find_order();
    solve_dp();
    print();
}

int main()
{
    read();
    solve();
    return 0;
}
