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

3 2 10 30
7 10 8
1 9
3 13

83

Dla przykładu powyżej, w celu zmaksymalizowania zysków należy wycofać rezerwację trzech biletów z drugiej rezerwacji.

Autor zadania: Piotr Stańczyk.