거미는 어떻게 물 위를 걸을까?

어떤 종류의 거미는 물 위를 걸을 수 있지만, 폭포 근처를 걸을 때는 위험에 빠질 수 있다.

연못이나 강의 잔잔한 부분의 물은 거미가 걷기에 적합하다. 거미는 물이 움직이는 것을 느끼면 반대 방향으로 뛴다. 위험한 점은 거미가 잔잔한 물에서 멀어질수록 물의 속도가 점점 빨라진다는 것이다. 거미는 물의 속도가 자신의 점프 능력 $P$ 이하인 동안에는 물살을 거슬러 걸을 수 있다.

폭포는 물의 속도를 급격히 증가시킨다. 따라서 폭포 바로 앞의 물이 거미의 점프 능력보다 느리게 움직이면, 거미는 폭포를 감지하지 못하고 떨어질 수 있다. 잔잔한 물로 쉽게 돌아갈 수 있다고 믿기 때문이다. 만약 거미가 물의 속도가 자신의 점프 능력보다 큰 구간을 걷는다면, 거미는 떨어진다.

보통 폭포 근처의 물 속도는 특정한 규칙을 따르지 않지만, 어떤 경우에는 잔잔한 물로부터 거리 $m$에서의 물 속도가 거리 $m - 1$과 $m - 2$에서의 속도에 선형적으로 의존한다는 것이 밝혀졌다. 그런 경우에는 처음 몇 미터의 속도를 측정해 두었으므로, 폭포까지 각 지점의 속도를 계산할 수 있다.

우리는 거미가 도달했다가 안전하게 돌아올 수 있는, 폭포까지의 최소 거리를 알고 싶다.

입력은 여러 개의 경우로 이루어지며, 한 줄에 하나씩 주어진다. 각 경우는 여러 개의 정수 $D, P, S_0, S_1, S_2, \dots$로 주어진다.

$D$는 잔잔한 물에서 폭포까지의 거리(미터)이다 ($2 < D \le 10000$). $P$는 거미의 점프 능력이다 ($1 < P \le 1000$). 나머지 수들은 거미가 폭포에 다가갈 때의 물 속도이다. $S_0$은 잔잔한 물 구역에서의 속도, $S_1$은 잔잔한 물에서 $1$미터 떨어진 지점의 속도, $S_2$는 $2$미터 떨어진 지점의 속도이며, 이런 식으로 이어진다. 경우에 따라 이 목록은 더 길어질 수 있으며, 최대 $D + 1$개의 값이 주어진다. 속도가 알려진 규칙을 따르지 않을 때에는 $D + 1$개의 값이 모두 주어지고, 그렇지 않으면 최소 네 개의 값이 주어진다. 모든 속도 수열은 감소하지 않으며, 모든 속도는 정수이다.

각 경우에 대해, 거미가 여전히 물 위에 있을 수 있는 폭포까지의 최소 거리를 정수로 한 줄에 출력한다. 이 거리는 $D - m$과 같으며, $m$은 $S_m \le P$를 만족하는 가장 큰 인덱스(거미가 안전하게 도달할 수 있는 가장 먼 위치)이다.

다만 다음의 경우에는 그 대신 아래 문구를 출력한다.

• 거미의 점프 능력이 폭포 바로 앞(거리 $D - 1$)의 물 속도보다 크거나 같으면, 거미가 폭포를 감지할 수 없으므로 The spider may fall!를 출력한다.
• 거미의 점프 능력이 연못이나 강(잔잔한 물)의 속도 $S_0$보다 작으면 The spider is going to fall!를 출력한다.