20928번 - 걷는 건 귀찮아

문제

일직선 위에 놓인 $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을 출력한다.

제한

노트