Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

POTKON1 - Konferencja

W Bitogrodzie trwają przygotowania do dorocznej Wielkiej Konferencji Bitonicznej. W ramach konferencji odbędzie się m 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 k uczestników. Liczba sal jest wystarczająca do pomieszczenia wszystkich prezentacji. Jeśli w prezentacji uczestniczy więcej niż k słuchaczy, to organizatorzy muszą zarezerwować większą liczbę 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 s. Bilet wstępu dla jednej osoby na i-tą prezentację kosztuje ci. Ceny biletów zostały tak dobrane, aby na pewno opłacalne było wynajęcie sali dla [k/2] ( gdzie, [x] - podłoga z liczby x, to największa liczby naturalna m taka, że m<=x) osób (ale być może opłaca się 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 programy, który:
  • wczyta ze standardowego wejścia ceny biletów, wielkości sal i koszy 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: m, l, k, s (1<=m<=100, 2<=l<=1 000 000, 2<=k<=400, 1<=s<=1000), pooddzielane pojedynczymi odstępami. Liczby te reprezentują odpowiednio: liczbę przeprowadzonych prezentacji, liczbę dokonanych rezerwacji, wielkość każdej z sal oraz koszt wynajęcia jednej sali. Drugi wiersz zawiera dokładnie m liczb 0<=ci <=s, pooddzielanych pojedynczymi odstępami. Są to ceny biletów na kolejne prezentacje. Kolejne l wierszy zawiera opisy dokonanych rezerwacji. Każda rezerwacja jest przez określona przez dwie liczby całkowite p oraz r (1<=p<=m, 1<=r<=1000), oddzielone pojedynczym odstępem. Reprezentują one odpowiednio numer prezentacji, na którą dokonywana jest rezerwacja oraz liczbę rezerwowanych biletów. Dozwolone jest wycofanie 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

    Wejście:
    3 2 10 30
    7 10 8
    1 9
    3 13
    
    Wyjście:
    83
    

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


  • Dodane przez:Marcin Sasinowski
    Data dodania:2007-04-18
    Limit czasu wykonania programu:1s
    Limit długości kodu źródłowego50000B
    Limit pamięci:1536MB
    Cluster: Cube (Intel G860)
    Języki programowania:All except: GOSU
    Pochodzenie:Potyczki algorytmiczne 2007 - Runda II [B]
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.