W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Twój przyjaciel jest właścicielem hotelu w Gdyni. Właśnie rozpoczyna się sezon turystyczny i do hotelu napłynęła przytłaczająca liczba ofert od potencjalnych klientów. Przyjaciel poprosił Cię więc o pomoc w przygotowaniu systemu rezerwacji pokoi hotelowych.
Do wynajęcia jest pokoi. Przygotowanie -tego spośród nich będzie kosztowało Twojego przyjaciela złotych (o ile zdecyduje się go wynająć). Wówczas pokój będzie można wynająć maksymalnie osobom. Można założyć, że koszt przygotowania pokoju o większej pojemności jest nie mniejszy niż koszt przygotowania dowolnego pokoju o mniejszej pojemności.
System rezerwacji otrzyma pewną liczbę ofert. Każda z nich będzie zawierała minimalną wymaganą pojemność pokoju ( osób) oraz cenę, jaką wynajmujący chce zapłacić za pokój ( złotych). Każdemu oferentowi można wynająć tylko jeden pokój, nie można też wynająć kilku klientom tego samego pokoju. Twój przyjaciel chciałby mieć w wakacje trochę czasu dla siebie, nie zamierza zatem przyjmować więcej niż ofert.
Skoro jesteś tak zdolnym programistą, Twój przyjaciel chciałby, abyś obliczył dla niego maksymalny możliwy zysk z wynajęcia pokoi. Zysk to całkowita suma, która wpłynie za wynajęte pokoje, pomniejszona o koszt ich przygotowania.
Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite , oraz (, ), oznaczające odpowiednio liczbę pokoi w hotelu, liczbę złożonych ofert oraz maksymalną liczbę ofert, którą przyjaciel jest w stanie przyjąć. Następne wierszy to opisy pokoi: -ty wiersz zawiera dwie liczby całkowite , () - koszt przygotowania i pojemność -tego pokoju. Kolejne wierszy to opisy ofert, każdy zawierający dwie liczby całkowite , () - wysokość -tej oferty oraz minimalny rozmiar wymaganego pokoju.
Możesz założyć, że w testach wartych 40 punktów zachodzi dodatkowa nierówność .
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą - maksymalny możliwy zysk z wynajęcia co najwyżej pokoi. Zauważ (i miej nadzieję!), że zysk może okazać się duży.
Dla danych wejściowych:
3 2 2 150 2 400 3 100 2 200 1 700 3
poprawną odpowiedzią jest:
400
Wyjaśnienie do przykładu: Twój przyjaciel może przyjąć obydwie oferty, wynajmując pokoje numer 2 i 3.
Autor zadania: Jakub Pachocki.