이진 로봇

로봇 시장에서 요즘 가장 인기 있는 상품은 "이진 로봇"이다. 이진 로봇은 항상 두 종류의 작업(예를 들어 바느질과 실 뜯기, 또는 먹기와 사색하기)을 할 수 있도록 설계되지만, 두 작업을 동시에 할 수는 없다. 드물게 하드웨어 고장으로 인해 단 한 가지 작업만 할 수 있는 로봇도 있다.

바이타자르는 이진 로봇을 빌려주는 회사를 운영한다. 그는 $n$대의 로봇을 보유하고 있으며, 각 로봇 $i$는 자신이 할 수 있는 작업들이 정해져 있고 대여 가격 $w_i$가 매겨져 있다. 바이타자르에게는 서로 다른 작업에 대한 대여 요청이 $m$건 들어왔다. 로봇 한 대를 빌려주면 그 로봇은 자신이 할 수 있는 작업 중 정확히 하나만 맡을 수 있고, 각 작업(요청)은 최대 한 대의 로봇에만 배정할 수 있다. 바이타자르는 모든 로봇을 빌려줄 필요도, 모든 요청을 받아들일 필요도 없다.

빌려준 로봇 한 대마다 그 로봇의 대여 가격만큼 수익이 생긴다. 바이타자르가 얻을 수 있는 최대 총수익을 계산하는 프로그램을 작성하여라.

첫째 줄에 세 정수 $n$, $m$, $q$ ($1 \le n, m \le 1\,000\,000$, $0 \le q \le 2n$)가 주어진다. 각각 로봇의 수, 처리할 작업(요청)의 수, 그리고 모든 로봇이 가진 능력의 총 개수이다. 로봇은 $1$부터 $n$까지, 작업은 $1$부터 $m$까지 번호가 매겨져 있다.

둘째 줄에는 $n$개의 정수 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1\,000\,000\,000$)이 주어지며, 각 로봇의 대여 가격을 뜻한다.

이어지는 $q$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le m$)가 주어진다. 이는 로봇 $a_i$가 작업 $b_i$를 수행할 수 있음을 의미한다. 어떤 쌍 $(a_i, b_i)$도 중복되어 나타나지 않는다. 또한 모든 $x = 1, 2, \dots, n$에 대해 $(x, y)$ 형태의 쌍이 정확히 한 번 또는 두 번 나타난다. 즉, 각 로봇은 한 가지 또는 두 가지 작업을 할 수 있다.

바이타자르가 얻을 수 있는 최대 총수익을 정수 하나로 출력하여라.