问题描述

津津是个勇敢的孩子， 总是做一些挑战自己的事情。 一天津津来到一条宽为 L 米的小河边， 河道的一边到另一边需要途径 N 块较大的石墩， 每块石墩到这一边岸边之间距离 $x_i$ 米（ 石墩不占距离， 只考虑石墩的中间点到这一边岸边之间距离） 。 津津想踩着这些石墩从小河的这一边跳到另一边（ 不落入水中） ， 一次可以跳过几块石墩。 已知津津每次最多跳 M 米的距离， 那么津津最少跳几次就能从这一边跳到另一边？

输入格式

第一行包含三个整数 L,N, M， 分别小河的宽度、 石墩数和津津跳的最远距离。

接下来 N 行， 每行一个整数， 第 i 行的整数 $d_i$( 0 <$d_i$< L)， 表示第 i 块石墩与这一边岸边的距离， 保证石墩之间的距离和石墩到这一边岸边的距离小等于 M。 这些石墩按与起点距离从小到大的顺序给出， 且不会有两个石墩出现在同一个位置。

输出格式

一个整数， 即最少的跳跃次数

样例

10 4 2
2
4
6
8

5

样例1说明

津津可以从岸边跳到距离为 2 石墩上， 然后跳到距离为 4 的石墩上， 再跳到距离为 6 的石墩上， 再跳到距离为 8 的石墩上， 最后跳的对岸。 总共 5 跳跃

25 5 10
2
11
14
17
21

4

样例2说明

津津可以从岸边跳到距离为 2 石墩上， 然后跳到距离为 11 的石墩上， 再跳到距离为 21 的石墩上， 最后跳的对岸。 总共 4 跳跃

数据范围

对于 30% 的数据,1≤N≤10。

对于 50% 的数据,1≤N≤100。

对于 100%的数据,1≤N≤500,1≤M,L≤1,000,000

来源

2020 NOIP 山东(小学组)