题目描述

汽车从起点出发驶向目的地，该目的地位于出发位置东面 $target$ 英里处。

沿途有加油站，用数组 $stations$ 表示。其中 $stations[i] = [position_i, fuel_i]$ 表示第 $i$ 个加油站位于出发位置东面 $position_i$ 英里处，并且有 $fuel_i$ 升汽油。

假设汽车油箱的容量是无限的，其中最初有 $startFuel$ 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 $-1$ 。

注意：如果汽车到达加油站时剩余燃料为 $0$，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 $0$，仍然认为它已经到达目的地。

输入格式

第一行三个空格隔开的整数分别表示 $target$、$startFuel$ 和加油站的数量 $n$；

接下来的 $n$ 行，每行两个空格隔开的正整数，表示每个加油站的位置和油量。

输出格式

一行一个整数表示答案。

示例 1：

1 1 0

0

解释: 可以在不加油的情况下到达目的地。

示例 2：

100 1 1
10 100

-1

解释: 无法抵达目的地，甚至无法到达第一个加油站。

示例 3：

100 10 4
10 60
20 30
30 30
60 40

2

解释:

出发时有 10 升燃料。

开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。

然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），

并将汽油从 10 升加到 50 升。然后开车抵达目的地。

沿途在两个加油站停靠，所以返回 2 。

提示：

• $1 <= target, startFuel <= 10^9$
• $0 <= stations.length <= 500$
• $1 <= position_i < position_{i+1} < target$
• $1 <= fuel_i < 10^9$

SOURCE

最低加油次数