题目描述

Johnny 驾驶着他的卡车。他必须从他的家乡去城区中心送一个物件。假设他家的位置在数轴上的原点 $O$，城区中心在点 $D$。

Johnny 的卡车有一个油箱，最多可以装 $N$ 升汽油，出发时，他的油箱里装满了汽油。当 Johnny 驾驶卡车时，每行驶 $1$ 个单位长度会消耗 $1\ \tt L$ 油。当然，在行驶的途中，有 $M$ 个加油站，第 $i$ 个加油站在数轴上表示 $x_i$ 的位置，并且每加 $1\ \tt L$ 油，要付 $p_i$ 美元的油钱。

Johnny 想知道，要完成接送任务，需要花多少美元。

输入格式

第一行输入 $D$，$N$ 和 $M$（$1≤N≤D≤10^9$，$1≤M≤2×10^5$）。

接下来 $M$ 行，第 $i$ 行有两个正整数代表加油站的位置 $x_i$（$1≤x_i≤D-1$）和单价 $p_i$（$1≤p_i≤10^6$）。

输出格式

输出仅一行，代表最少花费。如果不能完成则输出 $−1$。

10 4 4
3 5
5 8
6 3
8 4

22

16 5 2
8 2
5 1

-1