1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int LOGN = 19, N = 200001, K = 500000, INF = 1000000;

int s[LOGN][N];
int t[LOGN][N];

int in[N];
int out[N];

vector<int> tree[N];

int g[N];

int c[K];
int d[K];
pair<int, int> p[K];

void dfs(int v)
{
    static int time = 0;
    in[v] = ++time;
    for(auto u: tree[v])
	dfs(u);
    out[v] = ++time;
}

bool ancestor(int a, int b)
{
    return in[b] >= in[a] && out[b] <= out[a];
}

int time(int a, int b)
{
    if(!ancestor(s[LOGN-1][a], b)) return INF;
    int ans = 0;
    for(int i = LOGN - 1; i >= 0; i--)
    {
	if(!ancestor(s[i][a], b))
	{
	    ans = max(ans, t[i][a]);
	    a = s[i][a];
	}
	if(!ancestor(s[i][b], a))
	{
	    ans = max(ans, t[i][b]);
	    b = s[i][b];
	}
    }
    if(!ancestor(a, b)) ans = max(ans, t[0][a]);
    if(!ancestor(b, a)) ans = max(ans, t[0][b]);
    return ans;
}

int main()
{
    int n, m, k, a, b;
    long long ans = 0;
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
	scanf("%d", g + i);
    for(int i = 1; i <= m; i++)
    {
	scanf("%d %d", &a, &b);
	tree[b].push_back(a);
	s[0][a] = b;
	t[0][a] = i;
    }
    for(int i = 1; i <= n; i++)
	if(s[0][i] == 0)
	{
	    s[0][i] = i;
	    dfs(i);
	}
    for(int i = 1; i < LOGN; i++)
	for(int j = 1; j <= n; j++)
	{
	    s[i][j] = s[i-1][s[i-1][j]];
	    t[i][j] = max(t[i-1][j], t[i-1][s[i-1][j]]);
	}
    for(int i = 0; i < k; i++)
    {
	scanf("%d %d", c + i, d + i);
	p[i] = make_pair(time(c[i], d[i]), i);
    }
    sort(p, p + k);
    for(int i = 0; i < k; i++)
    {
	if(p[i].first == INF) break;
	a = c[p[i].second];
	b = d[p[i].second];
	int z = min(g[a], g[b]);
	ans += 2 * z;
	g[a] -= z;
	g[b] -= z;
    }
    printf("%lld\n", ans);
}