题目描述

题目译自 PA 2014 Runda 5 Fiolki

Bajtazar 是一名化学家。他正在进行一项实验，目标是制备特效药 X——一种能解决人类所有问题的药剂。

Bajtazar 拥有 $n$ 个小瓶，编号为 $1$ 到 $n$，其中装有不同的液体物质。编号为 $i$ 的小瓶中装有整数克数的物质 $i$。为了制备特效药 X，需要执行一个包含 $m$ 个步骤的序列。每个步骤是将某个小瓶的全部内容倒入另一个小瓶中（我们可以假设小瓶的容量足够大，并且在倒入过程中不会洒出一滴）。倒空的小瓶将被放置在架子上，不再用于实验的后续部分。

已知某些物质对会相互反应，形成沉淀物。对于每对反应的物质，每克第一种物质与每克第二种物质反应，生成两克沉淀物。反应会持续进行，直到其中一种反应物耗尽为止。沉淀物不会与其他物质反应，并且在实验结束前会一直附着在生成沉淀的小瓶壁上。某些反应的速度比其他反应快——如果多种物质同时存在于一个溶液中，物质对之间的反应会按照 Bajtazar 已知的固定顺序进行。在每个步骤后，Bajtazar 会等待目标小瓶中的物质完全反应后，才执行下一步。

Bajtazar 想知道制备特效药 X 的步骤序列是否是最优的。他希望了解在执行所有步骤后，有多少反应物被浪费了。因此，他请你帮助他计算沉淀物的总克数。

输入格式

输入数据的第一行包含三个整数 $n, m, k$ $(0 \leq m < n \leq 200000, 0 \leq k \leq 500000)$，分别表示小瓶数量（也是不同物质的数量）、实验步骤序列的长度以及相互反应形成沉淀的物质对数量。

第二行包含 $n$ 个整数 $g_{1}, g_{2}, \ldots, g_{n}$ $(1 \leq g_{i} \leq 10^{9})$，表示编号为 $i$ 的小瓶中初始物质 $i$ 的克数。

接下来的 $m$ 行描述制备特效药 X 的步骤序列：第 $i$ 行包含两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示第 $i$ 步是将编号为 $a_{i}$ 的小瓶内容倒入编号为 $b_{i}$ 的小瓶中。可以假设如果在某个步骤中倒空了某个小瓶，则该小瓶不会在后续步骤中被再次使用。

接下来的 $k$ 行描述相互反应形成沉淀的物质对：第 $i$ 行包含两个整数 $c_{i}, d_{i}$ $(1 \leq c_{i}, d_{i} \leq n, c_{i} \neq d_{i})$，表示如果物质 $c_{i}$ 和 $d_{i}$ 同时存在于一个小瓶中，则会发生反应并形成沉淀。物质对按照反应优先级顺序给出，即如果一个小瓶中同时存在至少两对可反应的物质，则最先输入的物质对会首先（并完全）反应。输入中的 $k$ 行中，无序对 $(c_{i}, d_{i})$ 不会重复。

输出格式

输出应只有一行，包含一个整数，表示执行整个实验步骤序列后形成的沉淀物总克数。

3 2 1
2 3 4
1 2
3 2
2 3

6