题目描述

化学家吉丽想要配置一种神奇的药水来拯救世界。

吉丽有 $n$ 种不同的液体物质，和 $n$ 个药瓶（均从 $1$ 到 $n$ 编号）。初始时，第 $i$ 个瓶内装着 $g_i$ 克的第 $i$ 种物质。

吉丽需要执行一定的步骤来配置药水，第 $i$ 个步骤是将第 $a_i$ 个瓶子内的所有液体倒入第 $b_i$ 个瓶子，此后第 $a_i$ 个瓶子不会再被用到。瓶子的容量可以视作是无限的。

吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是 $1$ 克 $c_i$ 物质和 $1$ 克 $d_i$ 物质生成 $2$ 克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。

当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。

吉丽想知道配置过程中总共产生多少沉淀。

输入格式

第一行三个整数 $n,m,k$，分别表示药瓶的个数（即物质的种数），操作步数，可以发生的反应数量。

第二行有 $n$ 个整数 $g_1,g_2,…,g_n$，表示初始时每个瓶内物质的质量。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示第 $i$ 个步骤。保证 $a_i$ 在以后的步骤中不再出现。

接下来 $k$ 行，每行是一对可以发生反应的物质 $c_i,d_i$，按照反应的优先顺序给出。同一个反应不会重复出现。

输出格式

输出总共产生的沉淀质量。

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

6

提示

对于 $100\%$ 的数据，$0\le m<n\le 2\times 10^5$，$0\le k\le 5\times 10^5$，$1\le g_i\le 10^9$，$1\le a_i,b_i,c_i,d_i\le n$，$a_i\ne b_i$，$c_i\ne d_i$。