#Q1048. 加油站

加油站

题目背景

小李是个热爱旅行的年轻人,最近他决定开着自己心爱的汽车去探索大江南北,感受祖国的大好河山。为了不让自己半路“趴窝”,他早早地准备好了行车路线,确保自己能够在加油站的帮助下顺利完成旅程。与此同时小李希望自己的旅游尽可能少得被加油所打断,所以在规划路线时,小李想找到一种加油方案,可以使得加油次数最少。

题目描述

已知加满油时,汽车最远能行驶nn公里,以及所有kk个加油站的位置,计算小李最少需要加油多少次,才能走完全程为mm公里的旅途。

输入要求

第一行输入两个数nnmmnn代表汽车在加满油之后最大行驶距离。mm代表终点的位置。

第二行输入一个数kk。代表加油站数量。

第三行输入kk个数,其中第ii个数xix_i代表第ii个加油站离起点的距离。(位置按升序排列)

输出要求

输出一个数,代表完成旅途最少需要加油的次数。 如果无法抵达终点,输出-1

样例

80 200
5
20 50 100 160 300

3
100 200
5
20 50 100 160 300
1
50 200
5
20 50 100 160 300
-1

数据规模与约定

100%100\%的输入数据,满足 0<n,m,xi<1e9,0<k<1000 < n,m,x_i < 1e9, 0 < k < 100