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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

typedef hash_map<int, int> MAP;
typedef hash_map<int, int>::iterator MAP_IT;
//typedef map<int, int> MAP;
//typedef map<int, int>::iterator MAP_IT;

struct Reaction{
	int a, b;
	int prior;
	
	Reaction() {}
	Reaction(int aa, int bb, int pp) : a(aa), b(bb), prior(pp) {}
	
	bool operator<(const Reaction &r) const { return prior < r.prior; }
};

typedef set<Reaction> SET;
typedef set<Reaction>::iterator SET_IT;

struct Move{
	int from, to;
	
	Move() {}
	Move(int a, int b) : from(a), to(b) {}
};

struct Glass{
	SET *reactions;
	MAP *hmap;
	
	Glass(){ 
		reactions = new SET; 
		hmap = new MAP(1); 
	}
	
	~Glass(){
		if(reactions != NULL) delete reactions;
		if(hmap != NULL) delete hmap;
	}
};

Glass *glasses;
vector<Move> moves;
int n, m, k;
long long result;

void merge(int from, int to){
	Glass &g1 = glasses[from];
	Glass &g2 = glasses[to];
	
	SET *rList = (g1.reactions->size() <= g2.reactions->size() ? g1.reactions : g2.reactions);
	bool rFirst = (rList == g1.reactions);
	SET_IT rEnd = rList->end();
	
	for(SET_IT it = rList->begin(); it != rEnd; it++){
		MAP_IT it1, it2;
		int a = it->a;
		int b = it->b;
		
		if(!rFirst){
			int tmp = a;
			a = b;
			b = tmp;
		}
		
		if((it2 = g2.hmap->find(b)) != g2.hmap->end() && (it1 = g1.hmap->find(a)) != g1.hmap->end()){
			int size1 = it1->second;
			int size2 = it2->second;
			int rSize = min(size1, size2);
			
			result += 2 * rSize;
			it1->second -= rSize;
			it2->second -= rSize;
			
			if(it1->second <= 0) g1.hmap->erase(it1);
			if(it2->second <= 0) g2.hmap->erase(it2);
		}
	}
	
	if(g1.reactions->size() <= g2.reactions->size()){
		//g2.reactions->insert(g1.reactions->begin(), g1.reactions->end());
		MAP_IT mEnd = g1.hmap->end();
		SET_IT sEnd = g1.reactions->end();
		
		for(SET_IT it = g1.reactions->begin(); it != sEnd; it++)
			if(g1.hmap->find(it->a) != mEnd)
				g2.reactions->insert(*it);
		
		delete g1.reactions;
		g1.reactions = NULL;
	}else{
		//g1.reactions->insert(g2.reactions->begin(), g2.reactions->end());
		MAP_IT mEnd = g2.hmap->end();
		SET_IT sEnd = g2.reactions->end();
		
		for(SET_IT it = g2.reactions->begin(); it != sEnd; it++)
			if(g2.hmap->find(it->a) != mEnd)
				g1.reactions->insert(*it);
		
		delete g2.reactions;
		g2.reactions = g1.reactions;
		g1.reactions = NULL;
	}
	
	if(g1.hmap->size() <= g2.hmap->size()){
		g2.hmap->insert(g1.hmap->begin(), g1.hmap->end());
		delete g1.hmap;
		g1.hmap = NULL;
	}else{
		g1.hmap->insert(g2.hmap->begin(), g2.hmap->end());
		delete g2.hmap;
		g2.hmap = g1.hmap;
		g1.hmap = NULL;
	}
}

int main(){
	int g, a, b;
	
	scanf("%d%d%d", &n, &m, &k);
	
	glasses = new Glass[n + 1];
	
	for(int i=1; i<=n; i++){
		scanf("%d", &g);
		(*glasses[i].hmap)[i] = g;
	}
	
	for(int i=0; i<m; i++){
		scanf("%d%d", &a, &b);
		moves.push_back(Move(a, b));
	}
	
	for(int i=1; i<=k; i++){
		scanf("%d%d", &a, &b);
		glasses[a].reactions->insert(Reaction(a, b, i));		
		glasses[b].reactions->insert(Reaction(b, a, i));
	}
	
	result = 0;
	
	for(int i=0; i<(int)moves.size(); i++){
		Move &move = moves[i];
		merge(move.from, move.to);
	}
	
	printf("%lld\n", result);
	
	delete [] glasses;
	
	return 0;
}