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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

struct reakcja
{
    int zkim, nr;

    friend bool operator < (reakcja a, reakcja b)
    {
        return a.nr<b.nr;
    }
};

int ile[200005], ojc[200005], stop[200005], gdzie[200005], zrob[500005], reakcyje[500005][2];
set<int> mam[200005];
vector<reakcja> reakcje[200005];
long long w;

void rob (int co)
{
    int x,y,z,v,r,todo=0;
    stop[co]=-1;

    x=ojc[co];

    if (!x)
        return;

    y=gdzie[co];
    z=gdzie[x];

    if (mam[y].size()>mam[z].size())
        swap(y,z);

    for (set<int>::iterator it=mam[y].begin(); it!=mam[y].end(); it++)
    {
        v=*it;

        for (vector<reakcja>::iterator it2=reakcje[v].begin(); it2!=reakcje[v].end(); it2++)
            if (mam[z].find(it2->zkim)!=mam[z].end())
                zrob[todo++]=it2->nr;
    }

    sort(zrob,zrob+todo);

    for (int i=0; i<todo; i++)
    {
        y=reakcyje[zrob[i]][0];
        z=reakcyje[zrob[i]][1];
        r=min(ile[y],ile[z]);
        w+=(long long)r*2;
        ile[y]-=r;
        ile[z]-=r;
    }

    y=gdzie[co];
    z=gdzie[x];

    if (mam[y].size()>mam[z].size())
    {
        gdzie[x]=y;

        while (!mam[z].empty())
        {
            mam[y].insert(*mam[z].begin());
            mam[z].erase(mam[z].begin());
        }
    }
    else
    {
        while (!mam[y].empty())
        {
            mam[z].insert(*mam[y].begin());
            mam[y].erase(mam[y].begin());
        }
    }

    stop[x]--;

    if (!stop[x])
        rob(x);
}

int main ()
{
    int n,m,k,a,b,c,d;
    reakcja kaka;

    scanf ("%d%d%d", &n, &m, &k);

    for (a=1; a<=n; a++)
    {
        scanf ("%d", &ile[a]);
        mam[a].insert(a);
        gdzie[a]=a;
    }

    for (a=0; a<m; a++)
    {
        scanf ("%d%d", &b, &c);
        ojc[b]=c;
        stop[c]++;
    }

    for (a=0; a<k; a++)
    {
        scanf ("%d%d", &b, &c);
        reakcyje[a][0]=b;
        reakcyje[a][1]=c;
        kaka.nr=a;
        kaka.zkim=c;
        reakcje[b].push_back(kaka);
        kaka.zkim=b;
        reakcje[c].push_back(kaka);
    }

    for (a=1; a<=n; a++)
        if (stop[a]==0)
            rob(a);

    printf ("%lld", w);

    return 0;
}