Roboty binarne

Limit pamięci: 64 MB

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 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 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.

Wejście

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

W drugim wierszu wejścia znajduje się ciąg liczb całkowitych (), które oznaczają ceny za wynajęcie kolejnych robotów.

Następne wierszy zawiera po dwie liczby całkowite , (, ) oznaczające, że robot może wykonać pracę . Żadna para nie powtarza się. Dla każdego , na wejściu pojawi się jedna lub dwie pary postaci (,).

Wyjście

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

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

7

Autor zadania: Mateusz Litwin.