Konferencja [B]
Limit pamięci: 32 MB
W Bitogrodzie trwają przygotowania do dorocznej Wielkiej Konferencji
Bitonicznej. W ramach konferencji odbędzie się prezentacji, które -
zgodnie z tradycją - muszą odbywać się dokładnie w tym samym czasie. Wszystkie
prezentacje przeprowadzane są w identycznych salach. Każda sala jest w stanie
pomieścić co najwyżej uczestników.
Liczba sal jest wystarczająca do pomieszczenia wszystkich prezentacji.
Jeśli w prezentacji uczestniczy więcej
niż słuchaczy, to organizatorzy muszą zarezerwować odpowiednio większą
liczbę sal (dokładniej, dla uczestników wymagane jest przygotowanie 1 sal).
Organizatorzy konferencji chcą zmaksymalizować
swoje zyski - suma uzyskana ze sprzedaży biletów, pomniejszona o koszt
wynajęcia sal, powinna być jak największa. Koszt wynajmu każdej z sal jest równy
. Bilet wstępu dla jednej osoby na -tą
prezentację kosztuje . Ceny biletów zostały
tak dobrane, aby na pewno opłacalne było wynajęcie sali dla osób (ale być może opłaca się to również dla mniejszej liczby osób),
czyli zysk z wynajęcia jest w takim przypadku nieujemny.
Organizatorzy chcą unieważnić niektóre zarezerwowane bilety w
celu zmaksymalizowania zysków. Ponieważ Ty pisałeś system rejestracji na
konferencję, zatem Tobie przypadło w udziale wykonanie tego zadania.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia ceny biletów, wielkości sal i koszty ich
wynajęcia oraz listę dokonanych rezerwacji,
-
wyznaczy maksymalny zysk z konferencji, jaki można uzyskać poprzez
wycofanie niektórych zarezerwowanych biletów,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite: , ,
, (, ,
, ), pooddzielane pojedynczymi odstępami.
Liczby te reprezentują 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 w tym zapisie wynika z zyskowności 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. Dozwolone jest wycofywanie dowolnej liczby
zarezerwowanych biletów, a nie tylko pełnych rezerwacji.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę
całkowitą - maksymalny zysk z konferencji, na jaki mogą liczyć
organizatorzy.
Przykład
Dla danych wejściowych:
3 2 10 30
7 10 8
1 9
3 13
poprawną odpowiedzią jest:
83
Dla przykładu powyżej, w celu zmaksymalizowania zysków należy wycofać rezerwację trzech biletów z drugiej rezerwacji.
1. Symbol
oznacza najmniejszą liczbę
całkowitą nie mniejszą od
. Analogicznie, symbol
oznacza największą liczbę całkowitą nie większą od
.
Autor zadania: Piotr Stańczyk.