IV Olimpiada Informatyczna 1996/97

Zadanie: PAL
Autor: Tomasz Śmigielski
PALIWO

Zawody II stopnia  
Plik źródłowy: PAL.??? (np. pas, c, cpp)
Plik wykonywalny: PAL.exe
Plik wejściowy: PAL.in
Plik wyjściowy: PAL.out

Firma transportowa X otrzymała nowe zlecenie; będzie dostarczała paczki z miasta A do miasta B. Paczki będą przewożone samochodami firmy. Na trasie AB jest wiele stacji benzynowych oferujących paliwo po różnych cenach. Pierwsza z nich znajduje się na początku trasy. Wszystkie samochody firmy X zużywają jednakowo standardową jednostkę paliwa na przejechanie jednej mili, ale mają różne pojemności zbiorników. Koszt paliwa potrzebnego do przejechania trasy AB zależy od pojemności zbiornika na paliwo w samochodzie i wybranego planu tankowania paliwa na stacjach leżących wzdłuż trasy. Zakładamy, że na każdej stacji jest zawsze wystarczająco dużo paliwa, by kierowca mógł napełnić zbiornik do pełna oraz że leżą one dostatecznie gęsto, aby każdy samochód firmy X mógł przejechać całą trasę.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku tekstowego PAL.IN jest zapisana pojemność p zbiornika samochodu. Jest to liczba całkowita spełniająca nierówność 1 < p <= 1000000.

W drugim wierszu jest zapisana liczba n stacji benzynowych na trasie AB. Jest to liczba całkowita spełniająca nierówność 1 < n <= 1000000.

W każdym z kolejnych n wierszy jest zapisana para liczb całkowitych dodatnich, oddzielonych pojedynczym odstępem ci, di. Liczba ci - to cena standardowej jednostki paliwa na stacji i (licząc od A do B), zaś di - to odległość tej stacji w milach od następnej stacji w kierunku B (dn - to odległość ostatniej stacji od końca trasy AB). Liczby te spełniają nierówności: 1 <= ci <= 1000, 1 <= di <= 1000000.

Długość trasy AB (suma di) jest nie większa niż 1000000.

Wyjście

W pliku tekstowym PAL.IN należy zapisać jedną liczbę całkowitą - minimalny koszt tankowania paliwa na trasie AB dla samochodu o danej pojemności zbiornika.

Przykład

Dla pliku PAL.IN
40
3
2 10
1 15
2 5
poprawnym rozwiązaniem jest plik PAL.OUT:
40

Twój program powinien szukać pliku PAL.IN w katalogu bieżącym i tworzyć plik PAL.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę PAL.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku PAL.EXE.