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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

long long result;
int n, m, k, a, b, c;

int gram[200005];
int r1[200005];
int r2[200005];

vector <int> reakcje;
vector <int> v[200005];
vector <int>::iterator it;

struct pary
{
	int x, y, rep;
};

pary tab[1200005];
int ile[200005];

int main ()
{
	scanf("%d%d%d", &n, &m, &k);
	if (m == 0)
	{
		printf("0\n");
		return 0;
	}
	if (k == 0)
	{
		printf("0\n");
		return 0;
	}
	k *= 2;
	k += n;
	for (int i = 1; i <= n; ++i) scanf("%d", &gram[i]);
	for (int i = 0; i < m; ++i) scanf("%d%d", &r1[i], &r2[i]);
	for (int i = 1; i <= n; ++i)
	{
		tab[i].x = i;
		tab[i].rep = i;
		ile[i] = 1;
		v[i].push_back(i);
	}
	if (n % 2 == 0)
	{
		n++;
		k++;
	}
	for (int i = n + 1; i <= k; i += 2)
	{
		scanf("%d%d", &tab[i].x, &tab[i].y);
		tab[i].rep = tab[i].x;
		tab[i + 1].x = tab[i].y;
		tab[i + 1].y = tab[i].x;
		tab[i + 1].rep = tab[i].y;
		ile[tab[i].x]++;
		ile[tab[i].y]++;
		v[tab[i].x].push_back(i);
		v[tab[i].y].push_back(i + 1);
	}
	for (int i = 0; i < m; ++i)
	{
		a = tab[r1[i]].rep;
		b = tab[r2[i]].rep;
		if (ile[a] < ile[b])
		{
			c = a;
			a = b;
			b = c;
		}
		ile[a] += ile[b];
		for (it = v[b].begin(); it != v[b].end(); ++it)
		{
			c = *it;
			v[a].push_back(c);
			if ((c > n) && (tab[c ^ 1].rep == a)) reakcje.push_back(c);
			tab[c].rep = a;
		}
		v[b].clear();
		sort(reakcje.begin(), reakcje.end());
		for (it = reakcje.begin(); it != reakcje.end(); ++it)
		{
			c = *it;
			if (gram[tab[c].x] < gram[tab[c].y])
			{
				result += (LL)(2 * gram[tab[c].x]);
				gram[tab[c].y] -= gram[tab[c].x];
				gram[tab[c].x] = 0;
			}
			else
			{
				result += (LL)(2 * gram[tab[c].y]);
				gram[tab[c].x] -= gram[tab[c].y];
				gram[tab[c].y] = 0;
			}
		}
		reakcje.clear();
	}
	printf("%lld\n",result);
	return 0;
}