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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <vector>
#include<iostream>
#include<algorithm>
#define MAX 500003
#define LOGN 19

using namespace std;

vector<int> V[MAX];
int P[LOGN][MAX], treeSize[MAX];
bool vis[MAX];
int glebokosc[MAX];
int ojciec[MAX];
long long int tab[MAX];
int drzewon [MAX];
int aktualny_id[MAX];
int from, to, counter=1;
int pro [MAX] [4];
int kol [MAX];

int lca(int u, int v)
{
	if (glebokosc [u] < glebokosc [v]) while (glebokosc [u] != glebokosc [v]) v = ojciec [v];
	else while (glebokosc [v] != glebokosc [u]) u = ojciec [u];


	if (u == v) return u;
	while (u != v) {
		int t;
		t = 1;
		for (; P [t] [u] != P [t] [v]; t ++);
		t --;
		if (t == -1) return u;
		u = P [t] [u];
		v = P [t] [v];
	}
	return u;
}

void dfs(int v, int akt_glebokosc, int drzewo)
{
	glebokosc[v]=akt_glebokosc;
	drzewon [v] = drzewo;
	P [0] [v] = ojciec [v];
	for (int i = 0; i < V[v].size (); i ++) {
		dfs (V [v] [i], akt_glebokosc+1, drzewo);
	}
}

bool cmp (int l1, int l2) {
	if (glebokosc [pro [l1] [3]] > glebokosc [pro [l2] [3]]) return true;
	else if (glebokosc [pro [l1] [3]] == glebokosc [pro [l2] [3]]) {
		if (pro [l1] [2] < pro [l2] [2]) return true;
		else return false;
	}
	else return false;
}

int main()
{
	ios::sync_with_stdio (false);
	int n=0, m=0, k=0, id;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) cin>>tab[i];
	for(int i=1;i<=n;i++) aktualny_id[i]=i;
	id = n+1;

	for(int i = 0; i < m; ++i) {
		cin >> from >> to;


		V[id].push_back(aktualny_id [to]);
		V[id].push_back(aktualny_id [from]);
		ojciec [aktualny_id [to]] = id;
		ojciec [aktualny_id [from]] = id;


		aktualny_id[from]=id;
		aktualny_id[to]=id;

		id++;
	}
	n = id+1;


	for (int i = 1; i <= n; i ++) {
		if (ojciec [i] == 0) {
			P [0] [i] = i;
			dfs (i, 1, i);
		}
	}




	for(int i = 1; i <= LOGN; ++i)
		for(int j = 1; j <= n; ++j)
			P[i][j]=P[i-1][P[i-1][j]];

	for (int i = 0; i < k; i ++) {
		cin >> pro [i] [0] >> pro [i] [1];
		pro [i] [2] = i;
		if (drzewon [pro [i] [0]] == drzewon [pro [i] [1]]) pro [i] [3] = lca (pro [i] [0], pro [i] [1]);
		else pro [i] [3] = -1;
		kol [i] = i;
	}
	sort (kol, kol + k, cmp);
	long long osad = 0;
	int minimum;
	for (int i = 0; i < k; i ++) {
		if (pro [kol[i]] [3] != -1) {
			minimum = min (tab [pro [kol[i]] [0]], tab [pro [kol[i]] [1]]);
			tab [pro [kol[i]] [0]] -= minimum;
			tab [pro [kol[i]] [1]] -= minimum;
			osad += 2*minimum;
		}
	}
	cout << osad << endl;
	return 0;
}