1223 - 最低加油次数
Time Limit : 1 秒
Memory Limit : 128 MB
汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。
沿途有加油站,每个 station[i] 代表一个加油站,它位于出发位置东面 station[i][0] 英里处,并且有 station[i][1] 升汽油。
假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。
当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。
为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1 。
注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。
Input
第一行为3个整数,分别为目标点距离target,起始燃料数startFuel,加油站数量n
以下n行,每行2个数据,分别表示加油站距离和加油的数量
Output
到达目的地,汽车所必要的最低加油次数。
如果无法到达目的地,则返回 -1
Examples
Input
100 10 4 10 60 20 30 30 30 60 40
Output
2
Hint
1 \leq target, startFuel, stations[i][1] \leq 10^9
0 \leq stations.length \leq 500
0 < stations[0][0] < stations[1][0] < \cdots < stations[stations.length-1][0] < target