시훈이는 길이 N의 눈길을 걸어가려고 한다.

눈길은 길이 1 단위로 N칸으로 나누어져 있으며 i번째 칸의 눈의 깊이는 a_i이다.

시훈이는 1번 칸에서 출발해 N번 칸으로 이동하려고 한다.

시훈이는 Q개의 부츠를 가지고 있다.

i번째 부츠를 신으면 깊이가 s_i 이하인 칸들을 밟을 수 있고 한 걸음에 최대 d_i 칸을 이동할 수 있다.

각 부츠마다 시훈이가 그 부츠를 신고 출발했을 때 N번째 칸으로 이동할 수 있을지 계산해주자.

장화 timer 2s memory 512MB

장화 2s 512MB