시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 305 75 70 29.289%

문제

일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 

세상에서 걷는 게 제일 귀찮은 현솔이는 목적지인 $M$까지 걷지 않고 인력거만을 타면서 이동하고 싶다. 첫 번째 인력거에 타고 있는 현솔이가 목적지까지 가기 위한 인력거의 최소 환승 횟수를 알아 내보자.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$, $1 \le M \le 1\,000\,000$)

둘째 줄에 각 지점의 위치 $p_1$, $p_2$, $...$ , $p_N$이 공백으로 구분되어 오름차순으로 주어진다. ($1 \le p_1 \lt p_2 \lt ... \lt p_N \le 1\,000\,000$, $p_1 \le M$)

셋째 줄에 각 인력거꾼의 최대 이동 거리 $x_1$, $x_2$, $...$ , $x_N$이 공백으로 구분되어 순서대로 주어진다. ($1 \le x_i \le 10\,000$)

출력

현솔이가 걷지 않고 목적지까지 가기 위한 인력거의 최소 환승 횟수를 출력한다. 만약 도달할 수 없다면, -1을 출력한다.

예제 입력 1

3 9
1 3 5
5 5 4

예제 출력 1

1

예제 입력 2

3 11
1 3 5
5 5 4

예제 출력 2

-1