Minimum Number of Jumps Across Stones

Jinjin is a brave child who loves challenges. One day, he arrived at a small river with a width of \(L\) meters. To cross the river from one bank to the other, there are \(N\) large stone pillars placed in between. The distance of the center of the \(i\)-th stone from the starting bank is given as \(d_i\) meters (the stones themselves do not take up any distance).

Jinjin wants to step on these stones to jump from one bank to the other without falling into the water. In each jump, he can skip one or more stones, but his maximum jump distance cannot exceed \(M\) meters. Determine the minimum number of jumps Jinjin needs to make to cross the river. If it is impossible for him to cross, output -1.

Note: Assume that Jinjin starts at position 0 (the starting bank) and the opposite bank is at position \(L\). The stones' positions may be given in any order. You may sort them as needed.

inputFormat

The first line contains three integers: \(L\) (the width of the river in meters), \(N\) (the number of stones), and \(M\) (the maximum distance Jinjin can jump in one move).

The second line contains \(N\) space-separated integers, where the \(i\)-th integer represents the distance \(d_i\) from the starting bank to the center of the \(i\)-th stone.

outputFormat

Output a single integer representing the minimum number of jumps required for Jinjin to cross the river. If it is impossible for him to reach the other side, output -1.

sample

10 4 3
2 5 7 9

4