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

3 2 10 30
7 10 8
1 9
3 13

77

Autor zadania: Piotr Stańczyk.