W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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ę.
Napisz program, który:
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ż .
Na standardowe wyjście należy zapisać jedną liczbę całkowitą — minimalny koszt tankowania paliwa na trasie dla samochodu o danej pojemności zbiornika.
Dla danych wejściowych:
40 3 2 10 1 15 2 5
poprawną odpowiedzią jest:
40
Autor zadania: Tomasz Śmigielski.