Джонни управляет трактором и должен доставить посылку из одного города в другой. Оба города расположены на числовой прямой, при этом Джонни начинает в точке 0 и должен добраться до точки d.
Топливный бак трактора Джонни вмещает не больше чем n литров топлива и изначально заполнен до предела. На то, чтобы проехать одну единицу расстояния, тратится ровно один литр топлива. Вдоль пути расположены m заправок, при этом i-я заправка находится в точке xi и продаёт бензин по pi долларов за литр. Количество бензина на каждой заправке не ограничено. Определите минимальное количество денег, которое придётся потратить Джонни, чтобы доставить посылку.
Выходные данные
Выведите единственно целое число — минимальное количество денег, которое придётся потратить, чтобы доставить посылку из точки 0 в точку d. Если доставить посылку невозможно, то выведите -1.
Примечание
В первом примере топливный бак вмещает 4 литра. Джонни может проехать 3 единицы расстояния до первой заправки, залить там в бак 2 литра (в баке будет 3 литра топлива), проехать ещё 3 единицы расстояния до третьей заправки, купить там 4 литра топлива и доехать до конца. Итого придётся потратить 2·5 + 4·3 = 22 долларов.
Во втором примере Джонни никак не сможет доехать до пункта назначения, потому что у бака недостаточно объёма, чтобы доехать от последней заправки до точки d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 4 4
3 5
5 8
6 3
8 4
|
22
|
|
2
|
16 5 2
8 2
5 1
|
-1
|