Tanie hotele

Pasażerowie autokarów turystycznych, przewożących wycieczki transkontynentalną autostradą, spędzają w drodze wiele dni, zatem opłaty za noclegi stanowią poważną część kosztów podróży. Ze względu na bezpieczeństwo jazdy i wygodę pasażerów każdy autokar jedzie tylko w ciągu dnia i nie może przejechać więcej niż 800 km dziennie. Noce na trasie (poza jej początkiem i końcem) pasażerowie i kierowca spędzają w hotelach. Dotychczas planowano przejazdy tak, by liczba noclegów na trasie była jak najmniejsza. Dążąc do obniżki kosztów, przedsiębiorstwo przewozowe zdecydowało zbadać, czy opłaci się układanie planów podróży tak, by suma opłat za noclegi była możliwie najniższa, nawet gdyby to miało przedłużyć podróż. W tych obliczeniach można korzystać z ofert hoteli położonych przy autostradzie. W każdej ofercie jest podana odległość hotelu od początku trasy i cena jednego noclegu jednej osoby. Podróż jest tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża jeden raz. Nigdzie na trasie nie ma dwóch hoteli w jednym punkcie, więc dla zidentyfikowania hotelu wystarczy podać jego odległość od początku trasy. Nie planuje się noclegu na początku ani na końcu trasy. Liczba osób w autobusie nie zmienia się i w każdym hotelu wszyscy (łącznie z kierowcą) płacą za nocleg jednakowo - zgodnie z ofertą. Pojemność hoteli jest na tyle duża, że nie istnieje problem braku miejsc. Zawsze można liczyć na to, że w dowolnej chwili w każdym hotelu będzie wystarczająco dużo wolnych miejsc, by przenocować wszystkich pasażerów autobusu. Na każdym odcinku trasy o długości 800 km jest przynajmniej jeden hotel, co oznacza, że przejechanie trasy z zachowaniem podanych wyżej warunków jest możliwe.

Napisz program, który:

wczytuje ze standardowego wejścia dane: długość trasy, liczbę hoteli oraz oferty hoteli

znajduje najtańszy plan podróży, tzn. taki, żeby suma opłat za hotele była najmniejsza

zapisuje najmniejszą sumę opłat za hotele.

Wejście

W pierwszym wierszu standardowego wejścia są zapisane dwie liczby całkowite dodatnie, oddzielone pojedynczym odstępem: długość trasy d w kilometrach oraz liczba hoteli h, gdzie d<=16000 i h<=1000. W kolejnych h wierszach są zapisane oferty hoteli - każda oferta w osobnym wierszu. Są one uporządkowane według rosnącej odległości hoteli od początku trasy. Każda oferta jest zapisana w postaci dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem, pierwsza liczba - to odległość hotelu od początku trasy w kilometrach, a druga - to cena jednego noclegu w tym hotelu nie większa niż 1000.

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać najmniejszą sumę opłat za hotele jednego podróżnego.

Przykład

Wejście:
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40

Wyjście:
35