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.