Konferencja - poprawka [A]
Limit pamięci: 32 MB
Zapewne słyszałeś już o Wielkiej Konferencji Bitonicznej (jeśli nie, to zapoznaj się z
treścią zadania ""Konferencja"").
Organizatorzy WKB znów są w opałach i potrzebują Twojej pomocy.
Oryginalna wersja systemu rejestracyjnego pozwalała na zmaksymalizowanie zysków z konferencji
poprzez wycofywanie rezerwacji biletów (w celu zmniejszenia wydatków na wynajem sal konferencyjnych).
Takie podejście spotkało się jednak z przeciwem uczestników konferencji.
Nie są oni zadowoleni z sytuacji, w której organizatorzy wycofują część zarezerwowanych
w ramach pojedynczej rezerwacji biletów.
W związku z tym zostałeś poproszony o zmodyfikowanie systemu rejestracyjnego w taki sposób,
aby zmaksymalizować zyski z konferencji, dokonując jedynie wycofań pełnych rezerwacji.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia ceny biletów, wielkość każdej z sal i koszt
wynajęcia pojedynczej sali oraz listę dokonanych rezerwacji,
-
wyznaczy maksymalny zysk z konferencji, jaki można uzyskać poprzez
potencjalne wycofanie niektórych całych rezerwacji,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite: , ,
oraz (
, ,
, ),
pooddzielane pojedynczymi odstępami.
Reprezentują one odpowiednio: liczbę przeprowadzanych
prezentacji, liczbę dokonanych rezerwacji, wielkość każdej z sal oraz koszt wynajęcia
jednej sali. Drugi wiersz zawiera dokładnie liczb
(), pooddzielanych pojedynczymi odstępami
(dolne ograniczenie powyżej oznacza zyskowność wynajęcia sali dla
uczestników).
Są to ceny biletów na kolejne prezentacje. Kolejne wierszy zawiera opisy
dokonanych rezerwacji. Każda rezerwacja reprezentowana jest przez dwie liczby
całkowite oraz
(, ),
oddzielone pojedynczym odstępem. Reprezentują
one odpowiednio numer prezentacji, na którą dokonywana jest rezerwacja oraz
liczbę rezerwowanych biletów.
Podczas wycofywania rezerwacji nie jest dozwolone unieważnienie tylko części biletów.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą -
maksymalny zysk z konferencji, jaki można uzyskać wycofując niektóre pełne rezerwacje.
Przykład
Dla danych wejściowych:
3 2 10 30
7 10 8
1 9
3 13
poprawną odpowiedzią jest:
77
Autor zadania: Piotr Stańczyk.