C. Доставка посылки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джонни управляет трактором и должен доставить посылку из одного города в другой. Оба города расположены на числовой прямой, при этом Джонни начинает в точке 0 и должен добраться до точки d.

Топливный бак трактора Джонни вмещает не больше чем n литров топлива и изначально заполнен до предела. На то, чтобы проехать одну единицу расстояния, тратится ровно один литр топлива. Вдоль пути расположены m заправок, при этом i-я заправка находится в точке xi и продаёт бензин по pi долларов за литр. Количество бензина на каждой заправке не ограничено. Определите минимальное количество денег, которое придётся потратить Джонни, чтобы доставить посылку.

Входные данные

В первой строке входных данных записаны три целых числа d, n и m (1 ≤ n ≤ d ≤ 109, 1 ≤ m ≤ 200 000) — расстояние, которое необходимо проехать, объём топливного бака и количество заправок на пути соответственно.

В каждой из последующих m строк записаны два целых числа xi и pi (1 ≤ xi ≤ d - 1, 1 ≤ pi ≤ 106) — позиция i-й заправки и стоимость бензина в ней соответственно. Гарантируется, что координаты всех заправок различны.

Выходные данные

Выведите единственно целое число — минимальное количество денег, которое придётся потратить, чтобы доставить посылку из точки 0 в точку d. Если доставить посылку невозможно, то выведите -1.

Примеры
Входные данные
10 4 4
3 5
5 8
6 3
8 4
Выходные данные
22
Входные данные
16 5 2
8 2
5 1
Выходные данные
-1
Примечание

В первом примере топливный бак вмещает 4 литра. Джонни может проехать 3 единицы расстояния до первой заправки, залить там в бак 2 литра (в баке будет 3 литра топлива), проехать ещё 3 единицы расстояния до третьей заправки, купить там 4 литра топлива и доехать до конца. Итого придётся потратить 2·5 + 4·3 = 22 долларов.

Во втором примере Джонни никак не сможет доехать до пункта назначения, потому что у бака недостаточно объёма, чтобы доехать от последней заправки до точки d.