약병

바이타자르는 화학자다. 인류의 모든 문제를 풀어 주는 혼합물, 특효약 X를 만들려고 실험을 진행한다.

바이타자르에게는 $1$번부터 $n$번까지 번호가 붙은 약병 $n$개가 있고, 약병마다 서로 다른 액체 물질이 들어 있다. $i$번 약병에는 물질 $i$가 정수 그램만큼 들어 있다. 특효약 X를 얻으려면 $m$개의 단계를 순서대로 수행해야 한다. 한 단계는 어떤 약병의 내용물을 전부 다른 약병에 붓는 것이다. 약병의 용량은 충분히 크고, 붓는 동안 한 방울도 흘리지 않는다고 가정한다. 내용물을 부어낸 약병은 선반에 올려 두고 실험이 끝날 때까지 다시 쓰지 않는다.

어떤 물질 쌍은 서로 반응해 화합물을 만들고, 그 화합물은 앙금으로 가라앉는다. 반응마다 첫 번째 물질 $1$그램과 두 번째 물질 $1$그램이 만나 앙금 $2$그램이 생긴다. 반응은 두 반응물 중 하나가 다 떨어질 때까지 이어진다. 생긴 앙금은 어떤 물질과도 반응하지 않고, 실험이 끝날 때까지 자기가 생긴 약병 벽에 붙어 있다. 반응 속도는 쌍마다 다르다. 한 용액에 여러 물질이 한꺼번에 들어가면, 물질 쌍 사이의 반응은 바이타자르가 알고 있는 정해진 순서대로 일어난다. 바이타자르는 한 단계를 마칠 때마다 부어 넣은 약병 안의 물질이 다 반응할 때까지 기다렸다가 다음 단계를 수행한다.

바이타자르는 이 단계 순서가 최적인지 궁금하다. 그래서 반응물이 얼마나 낭비되는지 알고 싶다. 모든 단계를 끝냈을 때 생긴 앙금이 모두 몇 그램인지 구하라.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다 ($0 \le m < n \le 200000$, $0 \le k \le 500000$). 차례대로 약병의 개수(서로 다른 물질의 개수이기도 하다), 실험 단계의 개수, 반응해서 앙금을 만드는 물질 쌍의 개수다.

둘째 줄에 정수 $n$개 $g_1, g_2, \dots, g_n$이 주어진다 ($1 \le g_i \le 10^9$). $g_i$는 $i$번 약병에 처음 들어 있는 물질 $i$의 그램 수다.

이어지는 $m$개 줄은 단계를 순서대로 적은 것이다. 그중 $i$번째 줄에는 정수 $a_i$, $b_i$가 있고 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), $i$번째 단계에서 $a_i$번 약병의 내용물을 $b_i$번 약병에 붓는다는 뜻이다. 어떤 단계에서 내용물을 부어낸 약병은 그 뒤의 어떤 단계에도 나오지 않는다.

이어지는 $k$개 줄은 앙금을 만드는 물질 쌍을 적은 것이다. 그중 $i$번째 줄에는 정수 $c_i$, $d_i$가 있고 ($1 \le c_i, d_i \le n$, $c_i \ne d_i$), 물질 $c_i$와 $d_i$가 한 약병에 같이 있으면 둘 사이에 반응이 일어나 앙금이 생긴다는 뜻이다. 쌍은 반응 우선순위가 높은 것부터 주어진다. 즉 한 약병 안에 반응하는 쌍이 둘 이상 있으면, 입력에 먼저 나온 쌍의 반응이 먼저 시작해서 완전히 끝난 다음 그 다음 쌍의 반응이 시작한다. 순서를 무시했을 때 같은 쌍 $(c_i, d_i)$가 두 번 주어지는 일은 없다.

모든 단계를 끝냈을 때 생긴 앙금의 총 그램 수를 한 줄에 출력한다.