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
//BRUTE
#include <cstdio>
#include <set>
#include <map>
#include <algorithm>

using std::set;
using std::map;
using std::pair;
using std::min;
using std::sort;

struct Step
{
  int fromPhial;
  int toPhial;
};

struct Reaction
{
  int s1;
  int s2;
};

int n, m, k;
int substances[200001];
set<int> phials[200001];
Step steps[200001];
Reaction reactions[500000];
map<int, int> reactionsPerSubstance[200001];
int reactionsToMake[500000];
int reactionsToMakeSize;
long long int sediment;

void doStep(int fromPhialId, int toPhialId)
{
  set<int> & fromPhial = phials[fromPhialId];
  set<int> & toPhial = phials[toPhialId];

  reactionsToMakeSize = 0;
  for (set<int>::iterator fromSubstanceIndexIt = fromPhial.begin(); fromSubstanceIndexIt != fromPhial.end(); fromSubstanceIndexIt++)
  for (set<int>::iterator toSubstanceIndexIt = toPhial.begin(); toSubstanceIndexIt != toPhial.end(); toSubstanceIndexIt++)
  {
    map<int, int> & reactiveSubstances = reactionsPerSubstance[*fromSubstanceIndexIt];
    map<int, int>::iterator it = reactiveSubstances.find(*toSubstanceIndexIt);
    if (it != reactiveSubstances.end())
      reactionsToMake[reactionsToMakeSize++] = it->second;
  }
  
  toPhial.insert(fromPhial.begin(), fromPhial.end());
  fromPhial.clear();

  sort(reactionsToMake, reactionsToMake + reactionsToMakeSize);
  for (int rtmIndex = 0; rtmIndex < reactionsToMakeSize; rtmIndex++)
  {
    Reaction & r = reactions[reactionsToMake[rtmIndex]];
    int & quantity1 = substances[r.s1];
    int & quantity2 = substances[r.s2];
    int qmin = min(quantity1, quantity2);
    if (qmin == 0)
      continue;
    
    quantity1 -= qmin;
    if (quantity1 == 0)
      toPhial.erase(r.s1);
    
    quantity2 -= qmin;
    if (quantity2 == 0)
      toPhial.erase(r.s2);

    sediment += 2 * qmin;
  }
}

int main()
{
  sediment = 0;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", substances + i);
    phials[i].insert(i);
  }
  
  for (int i = 0; i < m; i++)
    scanf("%d%d", &(steps[i].fromPhial), &(steps[i].toPhial));

  int c, d;
  for (int i = 0; i < k; i++)
  {
    scanf("%d%d", &c, &d);
    reactions[i].s1 = c;
    reactions[i].s2 = d;
    reactionsPerSubstance[c].insert(pair<int, int>(d, i));
    reactionsPerSubstance[d].insert(pair<int, int>(c, i));
  }

  for (int i = 0; i < m; i++)
    doStep(steps[i].fromPhial, steps[i].toPhial);

  printf("%lld\n", sediment);

  return 0;
}