스케이트 질주 timer 2s memory 512MB

스케이트 연습을 마친 정올이는 스케이트를 타고 질주를 하려고 한다.

스케이트를 타고 질주하는 코스는 1번부터 N번까지 번호가 붙은 N개의 지점으로 구성되어 있다.

이 질주는 1번 지점에서 0의 속력으로 출발하여, N번 지점까지 번호가 증가하는 순서대로 방문하며 이어진다.

그 중 M개의 지점 X[0], X[1], ...\ , X[M-1] 지점에는 각각 속력 제한 V[0],V[1],...\ ,V[M-1]이 있어, X[i] 지점을 지날 때는 속력 제한 V[i]를 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다.

속력을 높이거나 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 최소 0에서 최대 K까지 변경하는 것이 가능하다.

즉, 마지막 방문 지점에서의 속도가 v였다면, 이번 방문하는 지점에서의 속도는 v-K에서 v+K 사이의 값이 가능하다는 의미다.

물론 속도를 그대로 유지하는 것도 가능하다.

스케이트 코스의 속력 제한이 주어졌을 때, 그 코스에서 정올이가 속도제한을 지키며 달릴 수 있는 최고 속도를 알아보자.