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

• wczytuje z pliku tekstowego PAL.IN następujące dane:
  • pojemność zbiornika na paliwo w samochodzie,
  • liczbę stacji benzynowych na trasie AB,
  • cenę paliwa na każdej stacji oraz odległości między kolejnymi stacjami,
• znajduje minimalny koszt tankowania paliwa na trasie AB dla samochodu o danej pojemności zbiornika,
• zapisuje wynik w pliku tekstowym PAL.OUT.

Wejście

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 c_i, d_i. Liczba c_i - to cena standardowej jednostki paliwa na stacji i (licząc od A do B), zaś d_i - to odległość tej stacji w milach od następnej stacji w kierunku B (d_n - to odległość ostatniej stacji od końca trasy AB). Liczby te spełniają nierówności: 1 <= c_i <= 1000, 1 <= d_i <= 1000000.

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

Wyjście

Przykład

40
3
2 10
1 15
2 5

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.