约翰尼驾驶一辆卡车,必须将包裹从他的家乡运送到地区中心。他的家乡位于数轴上的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 个加油站的位置和加油费用。保证加油站位置明确。
输出
打印一个整数 — 完成配送的最低成本。如果没有办法完成交付,则打印-1。
示例
输入 #1
10 4 4 3 5 5 8 6 3 8 4
输出 #1
22
输入 #2
16 5 2 8 2 5 1
输出 #2
-1
注意
在第一个示例中,Johnny 的卡车可容纳 4 升。他可以驾驶 3 辆汽车到第一个加油站,在那里购买 2 升汽油(使油箱总数达到 3 升),再驾驶 3 辆汽车到第三个加油站,在那里购买 4 升加满油箱,然后直接开车到区中心。他的总成本是 2·5 + 4·3 = 22 美元。
在第二个示例中,Johnny 无法到达地区中心,因为他的油箱无法容纳足够的汽油,无法将他从最近的加油站带到地区中心。