Paliwo

Limit pamięci: 32 MB

Firma transportowa X otrzymała nowe zlecenie; będzie dostarczała paczki z miasta do miasta . Paczki będą przewożone samochodami firmy. Na trasie 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 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:

• wczytuje ze standardowego wejścia następujące dane:
  • pojemność zbiornika na paliwo w samochodzie,
  • liczbę stacji benzynowych na trasie ,
  • cenę paliwa na każdej stacji oraz odległości między kolejnymi stacjami;
• znajduje minimalny koszt tankowania paliwa na trasie dla samochodu o danej pojemności zbiornika;
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana pojemność zbiornika samochodu. Jest to liczba całkowita spełniająca nierówność . W drugim wierszu jest zapisana liczba stacji benzynowych na trasie . Jest to liczba całkowita spełniająca nierówność .

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

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

Wyjście

Na standardowe wyjście należy zapisać jedną liczbę całkowitą — minimalny koszt tankowania paliwa na trasie dla samochodu o danej pojemności zbiornika.

Przykład

Dla danych wejściowych:

40
3
2 10
1 15
2 5

poprawną odpowiedzią jest:

40

Autor zadania: Tomasz Śmigielski.