Rezerwacje

Limit pamięci: 64 MB

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.

Wejście

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ść .

Wyjście

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.

Przykład

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.