← 返回题目列表

Codeforces · 627/C

C. 包裹递送

中文机器翻译题面 查看原题

约翰尼驾驶一辆卡车,必须将包裹从他的家乡运送到地区中心。他的家乡位于数轴上的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 无法到达地区中心,因为他的油箱无法容纳足够的汽油,无法将他从最近的加油站带到地区中心。