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

using namespace std;

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

unordered_map<pair<int, int>, int> reactionOrder;

bool firstComparator(const pair<int, int>& lhs, const pair<int, int>& rhs) {
  return lhs.first < rhs.first;
}

bool performRectionComparator(const pair<int, int>& lhs, const pair<int, int>& rhs) {
  return reactionOrder[lhs] < reactionOrder[rhs];
}

int main() {
  int n,m,k;
  scanf("%d%d%d", &n,&m,&k);
  vector<int> g(n);
  vector<pair<int, int> > steps(m);
  vector<pair<int, int> > react(k);
  vector<vector<int> > liquidInTubes(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d", &g[i]);
    liquidInTubes[i].push_back(i);
  }

  for (int i = 0; i < m; ++i) {
    int tmp1, tmp2;
    scanf("%d%d", &tmp1, &tmp2);
    tmp1--; tmp2--;
    steps[i] = make_pair(tmp1, tmp2);
  }

  for (int i = 0; i < k; ++i) {
    int tmp1, tmp2;
    scanf("%d%d", &tmp1, &tmp2);
    tmp1--; tmp2--;
    react[i] = make_pair(min(tmp1, tmp2), max(tmp1, tmp2));
    reactionOrder[react[i]] = i+1;
  }

  long long result = 0;

  for (int i = 0; i < m; ++i) {
    pair<int, int> step = steps[i];
    vector<int>& firstTube = liquidInTubes[step.first];
    vector<int>& secondTube = liquidInTubes[step.second];

//    cout << "step" << i <<": " << step.first << "("<<firstTube.size()<<") -> " << step.second <<"("<<secondTube.size()<<")"<<  endl;

    vector<pair<int, int> > reactionsToPerform;

    for (vector<int>::iterator it1 = firstTube.begin(); it1 != firstTube.end(); ++it1) {
      for (vector<int>::iterator it2 = secondTube.begin(); it2 != secondTube.end(); ++it2) {
        pair<int, int> reactPair = make_pair(min(*it1, *it2), max(*it1, *it2));
        unordered_map<pair<int, int>, int>::iterator reactIt = reactionOrder.find(reactPair);

        if (reactIt == reactionOrder.end())
          continue;

        reactionsToPerform.push_back(reactPair);
      }
    }
    sort(reactionsToPerform.begin(), reactionsToPerform.end(), performRectionComparator);

//     cout << elemToRem1 << " === " << elemToRem2 << endl;
    
    secondTube.insert(secondTube.end(), firstTube.begin(), firstTube.end());
    firstTube = vector<int>();

    for (vector<pair<int, int> >::iterator it = reactionsToPerform.begin(); it != reactionsToPerform.end(); ++it) {
      pair<int, int> reactionPair = *it;
      int minval = min(g[reactionPair.first], g[reactionPair.second]);
      if (minval == 0)
        continue;
      g[reactionPair.first] -= minval;
      g[reactionPair.second] -= minval;
      result += minval << 1;
      if (g[reactionPair.first] == 0) {
        vector<int>::iterator it = find(secondTube.begin(), secondTube.end(), reactionPair.first);
        secondTube.erase(it);
      }
      if (g[reactionPair.second] == 0) {
        vector<int>::iterator it = find(secondTube.begin(), secondTube.end(), reactionPair.second);
        secondTube.erase(it);
      }
    }
  }

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

}