English
Zadanie Paliwo (pal)
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.