Walking Is Annoying

Interview

Time limit1sMemory limit1024 MB

Summary

Given N rickshaws at sorted positions, each covering a range to its right, find the minimum number of transfers to reach point M without walking.

Level: Medium6 of 10
Topics: Greedy, BFS, Array, Two pointers
Solved: No attempts yet

Problem

On a line there are $N$ points $p_i$ , each with a rickshaw puller who can carry a passenger up to $x_i$ units. That is, the puller at $p_i$ takes the passenger to one of $p_i$ , $p_i+1$ , $p_i+2$ , $...$ , $p_i+x_i$ .

Hyeonsol, the laziest person in the world when it comes to walking, wants to reach the destination $M$ without walking, riding rickshaws only. Hyeonsol is already on the first rickshaw. Find the minimum number of rickshaw transfers needed to reach the destination.

Input

The first line gives $N$ and $M$ , separated by a space. ( $1 \le N \le 100\,000$ , $1 \le M \le 1\,000\,000$ )

The second line gives the positions $p_1$ , $p_2$ , $...$ , $p_N$ of the points, separated by spaces in increasing order. ( $1 \le p_1 \lt p_2 \lt ... \lt p_N \le 1\,000\,000$ , $p_1 \le M$ )

The third line gives the maximum travel distances $x_1$ , $x_2$ , $...$ , $x_N$ of the rickshaw pullers, separated by spaces in that order. ( $1 \le x_i \le 10\,000$ )

Output

Print the minimum number of rickshaw transfers Hyeonsol needs to reach the destination without walking. If the destination cannot be reached, print -1.

Examples2

Example 1
Input
```
3 9
1 3 5
5 5 4
```
Expected output
```
1
```
Example 2
Input
```
3 11
1 3 5
5 5 4
```
Expected output
```
-1
```