시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB43375.000%

문제

Na rynku robotów najnowszym krzykiem mody są roboty binarne. Robot binarny zawsze projektowany jest tak, aby mógł wykonywać dwa rodzaje prac (na przykład szycie i prucie, albo jedzenie i filozofowanie), przy czym nie potrafi wykonywać obu równocześnie. Czasem, na szczęście rzadko, robot, na skutek awarii sprzętowej, zdolny jest tylko do jednego zajęcia.

Bajtazar prowadzi firmę wypożyczającą roboty binarne. W swojej ofercie posiada n robotów, z których każdy ma określone zdolności i może być wynajęty za ustaloną cenę. Do Bajtazara napłynęło m ofert wynajmu robotów, każda z nich dotyczy innego rodzaju pracy. Wynajęty robot może zajmować się tylko jedną spośród czynności, które potrafi wykonywać. Każda oferta przeznaczona jest dla co najwyżej jednego robota. Bajtazar nie musi oczywiście wynająć wszystkich robotów, ani też przyjmować wszystkich ofert. Napiszże program, który obliczy, ile najwięcej może zarobić Bajtazar.

입력

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite n, m oraz q (1 ≤ n, m ≤ 1 000 000, 0 ≤ q ≤ 2n) oznaczające kolejno liczbę robotów, liczbę prac do wykonania oraz łączną liczbę umiejętności robotów. Roboty są ponumerowane liczbami od 1 do n, zaś prace — liczbami od 1 do m.

W drugim wierszu wejścia znajduje się ciąg n liczb całkowitych w1, w2, ..., wn (1 ≤ wi ≤ 1 000 000 000), które oznaczają ceny za wynajęcie kolejnych robotów.

Następne q wierszy zawiera po dwie liczby całkowite aibi (1 ≤ ain, 1 ≤ bim) oznaczające, że robot ai może wykonać pracę bi. Żadna para (ai, bi) nie powtarza się. Dla każdego x = 1, 2, ..., n, na wejściu pojawi się jedna lub dwie pary postaci (x, y).

출력

Twój program powinien wypisać na wyjście jedną liczbę całkowitą — maksymalny utarg Bajtazara.

예제 입력 1

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

예제 출력 1

7

출처

Camp > POI Training Camp > ONTAK 2011 5-1번