Bajtazar 是一位化学家。他正在进行一项实验，目标是获得“X 试剂”——一种能解决人类所有问题的混合物。

Bajtazar 拥有 $n$ 个编号从 $1$ 到 $n$ 的烧瓶，里面装有不同的液体物质。编号为 $i$ 的烧瓶中含有 $i$ 号物质，其质量为整数克。为了获得 X 试剂，需要执行 $m$ 个步骤。每一步都涉及将一个烧瓶中的所有内容物倒入另一个烧瓶中（我们可以假设烧瓶的容量足够大，且在倾倒过程中不会损失任何液体）。被倒空的烧瓶会被放回架子上，不再参与后续的实验。

已知某些物质对之间会发生反应，生成沉淀形式的化学化合物。对于每一对这样的反应，每 $1$ 克第一种物质会与 $1$ 克第二种物质反应，生成 $2$ 克沉淀。反应会持续进行，直到其中一种反应物耗尽为止。生成的沉淀不会与任何其他物质发生反应，并会一直附着在生成它的烧瓶壁上，直到实验结束。某些反应比其他反应进行得更快——如果多种物质同时出现在同一个烧瓶中，物质对之间的反应会按照 Bajtazar 已知的固定顺序进行。每一步操作后，Bajtazar 都会等待目标烧瓶中的物质反应完毕，然后再进行下一步。

Bajtazar 想知道获得 X 试剂的步骤序列是否是最优的。他想知道在执行所有步骤后，有多少质量的反应物被浪费了。因此，他请求你帮助计算生成的沉淀总质量（单位为克）。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($0 \le m < n \le 200\,000, 0 \le k \le 500\,000$)，分别表示烧瓶的数量（即不同物质的数量）、实验步骤序列的长度以及会发生反应生成沉淀的物质对数量。

第二行包含 $n$ 个整数 $g_1, g_2, \dots, g_n$ ($1 \le g_i \le 10^9$)，表示编号为 $i$ 的烧瓶中物质 $i$ 的初始质量（克）。

接下来的 $m$ 行描述了获得 X 试剂的步骤序列：第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示第 $i$ 步是将编号为 $a_i$ 的烧瓶中的内容物倒入编号为 $b_i$ 的烧瓶中。可以假设，如果在某一步中倒空了一个烧瓶，那么该烧瓶将不会在后续的任何步骤中使用。

接下来的 $k$ 行描述了会发生反应生成沉淀的物质对：第 $i$ 行包含两个整数 $c_i, d_i$ ($1 \le c_i, d_i \le n, c_i \neq d_i$)，表示如果物质 $c_i$ 和 $d_i$ 同时出现在同一个烧瓶中，它们之间就会发生反应并生成沉淀。物质对按反应优先级排序，即如果烧瓶中同时存在至少两对反应物质，则输入中出现较早的物质对将首先开始（并完全结束）反应。任何无序对 $(c_i, d_i)$ 在这 $k$ 行中不会重复出现。

输出格式

输出一行，包含一个整数，表示执行完整个实验步骤序列后生成的沉淀总质量。

样例

输入 1

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

输出 1

6