Trikontenerowiec

Limit pamięci: 32 MB

Kopalnia Glinek HyperMarsjańskich (KGHyM) wydobywa (na Marsie) czerwone glinki węglowo-krzemowe i prasuje je w płyty wygodne w transporcie. Każda płyta ma standardową szerokość i grubość, ale poszczególne płyty mogą się różnić wysokością i jakością materiału. Wyróżnia się 1000 klas jakości glinek i produkuje się płyty o wysokościach mm. Cena płyty zależy tylko od jakości materiału - nie jest natomiast ważna jej wysokość. Płyta z materiału klasy kosztuje galaktarów.

Trikontenerowiec galaktyczny, to rodzaj statku kosmicznego, który służy do przewozu płyt produkowanych przez KGHyM. Ładownia tego statku to hala, w której w podłodze zamontowano równolegle prowadnic na płyty - w każdej prowadnicy można umieścić tylko jedna płytę. Ładownia ma spadzisty strop (patrz rysunek), tzn. jej sufit w jednym końcu jest na wysokości mm, a w drugim na wysokości mm - oznacza to, że strop nad prowadnicą o numerze jest na wysokości milimetrów i można w niej umieszczać tylko płyty o wysokości mniejszej lub równej tej wartości. Na hałdach KGHyM leżą płyty w oczekiwaniu na transport, a do doku przybił właśnie trikontenerowiec i jego załoga rozpoczęła załadunek statku. Wiadomo, że kapitanowi zależy na zabraniu ładunku o jak największej sumarycznej wartości, ale jest ograniczony rozmiarami ładowni (niestety nie może przyciąć zbyt dużych płyt, gdyż po sprasowaniu płyty nie poddają się łatwo obróbce). Wiadomo także, że doświadczona załoga statku wybierze ładunek optymalnie zgodnie z zaleceniami kapitana. Przedstawiciel KGHyM musi zdecydować, ile ma zapłacić za ładunek kapitan statku.

Zadanie

Napisz program który:

• wczytuje rozmiar ładowni i rozmiary płyt leżących na hałdzie,
• oblicza, jaka jest maksymalna wartość ładunku, który można zabrać na statek,
• wypisuje maksymalną wartość ładunku.

Wejście

W pierwszym wierszu wejścia podane są liczby naturalne i oddzielone spacją (, ) - oznacza długość, maksymalną wysokość i jednocześnie liczbę prowadnic w ładowni, a jest liczbą płyt na hałdzie. W kolejnych wierszach znajdują się opisy płyt z hałdy - po jednym w wierszu. Każdy opis płyty to dwie liczby naturalne i oddzielone spacją (, ) - pierwsza liczba oznacza klasę jakości tworzywa płyty, a druga wysokość płyty w milimetrach. Uwaga: Wśród płyt na hałdzie mogą znajdować się takie, których wysokości są większe od maksymalnej dopuszczalnej wysokości ładowni statku.

Wyjście

W pierwszym i jedynym wierszu wyniku należy podać jedną liczbę - wartość optymalnego ładunku.

Przykład

Dla danych wejściowych:

10 5
2 1
3 2
5 2
2 10
3 10

poprawną odpowiedzią jest:

13