Iloraz inteligencji

Limit pamięci: 128 MB

Na Uniwersytecie Bajtockim można studiować jedynie dwa kierunki: matematykę i informatykę. Aktualnie na uniwersytecie uczy się studentów matematyki oraz studentów informatyki. Kierunki te są bardzo trudne i nie istnieje student kształcący się w obu z nich jednocześnie.

Rektor Bajtazar zna iloraz inteligencji każdego ze studentów. Na tej podstawie chciałby wyznaczyć zespół studentów, który poradzi sobie z najtrudniejszymi problemami ludzkości. Postanowił więc, że wybierze zespół o możliwie dużej sumie ilorazów inteligencji wszystkich członków.

Iloraz inteligencji to jednak nie wszystko. Dlatego rektor chciałby, aby wszyscy członkowie zespołu się znali. Wiadomo, że wszyscy studenci matematyki się znają. Podobnie, każdy student informatyki zna każdego innego studenta informatyki.

Pomóż rektorowi i napisz program, który wyznaczy zespół studentów o możliwie dużej sumie ilorazów inteligencji, w którym wszyscy się znają.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i (, ), które oznaczają odpowiednio liczbę studentów matematyki, liczbę studentów informatyki oraz liczbę par osób z różnych kierunków, które się znają.

Każdy z kolejnych wierszy zawiera opis jednej pary znajomych: -ty z tych wierszy zawiera dwie liczby całkowite i (, ) oznaczające, odpowiednio, numer studenta matematyki i numer studenta informatyki z -tej pary. Zarówno studentów matematyki, jak i studentów informatyki numerujemy liczbami całkowitymi, poczynając od .

W następnym wierszu znajduje się liczb całkowitych z przedziału od do , które oznaczają ilorazy inteligencji kolejnych studentów matematyki. Kolejny wiersz zawiera liczb opisujących ilorazy inteligencji studentów informatyki, w analogicznym formacie.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą równą maksymalnej możliwej do uzyskania sumie ilorazów inteligencji w zespole, który spełnia oczekiwania Bajtazara.

Drugi wiersz powinien zawierać jedną liczbę całkowitą, będącą liczbą studentów matematyki, których powinien wybrać Bajtazar. W trzecim wierszu należy wypisać numery tych studentów (w dowolnej kolejności). Jeżeli w zespole nie ma żadnych studentów, należy wypisać pusty wiersz.

W kolejnych dwóch wierszach należy podać numery studentów informatyki wyznaczonych do zespołu, w analogicznym formacie.

W przypadku, gdy istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Przykład

Dla danych wejściowych:

3 2 3
1 1
2 1
2 2
1 3 1
1 2

poprawną odpowiedzią jest:

6
1
2
2
1 2

Autor zadania: Marek Cygan.