CF627C Package Delivery

Johnny 开着卡车，需要将一个包裹从他的家乡运送到区中心。他的家乡位于数轴上的 $0$ 点，区中心位于 $d$ 点。 Johnny 的卡车油箱最多可容纳 $n$ 升油，且出发时油箱是满的。在行驶过程中，卡车每行驶一个单位距离就消耗一升油。此外，路上有 $m$ 个加油站，分布在前往区中心的不同位置。第 $i$ 个加油站位于数轴的 $x_i$ 处，售价为 $p_i$ 美元每升油，可以无限购买。请你计算 Johnny 成功完成配送所需支付的最小总油费。

输入的第一行包含三个以空格分隔的整数 $d$、$n$ 和 $m$（$1 \leq n \leq d \leq 10^9$，$1 \leq m \leq 200\,000$），分别代表家乡到区中心的总距离、油箱容量、以及加油站数量。 接下来的 $m$ 行每行包含两个整数 $x_i$ 和 $p_i$（$1 \leq x_i \leq d - 1$，$1 \leq p_i \leq 10^6$），表示第 $i$ 个加油站的位置和油价。保证所有加油站的位置两两不同。

输出一个整数——完成配送所需的最小油费。如果无法完成配送，则输出 $-1$。

在第一个样例中，Johnny 的卡车油箱容量为 $4$ 升。可以先行驶 $3$ 个单位到第一个加油站，在此处加 $2$ 升油（此时油箱有 $3$ 升），再行驶 $3$ 个单位到第三个加油站，在那里加满 $4$ 升油，然后直接驶向区中心。总油费为 $2 \times 5 + 4 \times 3 = 22$ 美元。 在第二个样例中，由于最后一个加油站到区中心的距离大于油箱容量，Johnny 无法到达终点。 由 ChatGPT 5 翻译