반딧불이가 석순(바닥에서 솟아오르는)과 종유석(천장에 매달린) 등 장애물이 가득한 동굴로 날아들어왔습니다.

동굴의 길이는 N 이고 높이는 H 입니다. 첫 번째 장애물은 항상 석순이고 그 후로는 종유석과 석순이 번갈아 나타나는 형태입니다.

다음은 길이 14, 높이 5의 동굴의 예입니다 (이미지는 두 번째 예에 해당):

반딧불이는 장애물 주위를 날아다니는 타입이 아니라, 강력한 쿵푸 동작으로 동굴의 한 쪽 끝에서 다른 쪽 끝까지 높이와 양을 선택하여 모든 장애물을 파괴할 것입니다.

만약 반딧불이가 지면으로 부터 4번째 위치에 해당하는 높이를 선택하면 반딧불이는 총 8개의 장애물을 파괴합니다:

이것은 최선의 선택이 아닙니다. 왜냐하면 반딧불이가 높이 1이나 높이 5 중 하나를 선택하면 덜 피곤할 것이기 때문입니다.

그런 경우에는 오직 7개의 장애물만을 파괴하면 되기 때문입니다.

동굴의 길이와 높이, 그리고 모든 장애물의 크기가 주어졌을 때, 반딧불이가 동굴 끝에 도달하기 위해 파괴해야 하는 최소 장애물 수와 그 수를 달성할 수 있는 높이의 수를 출력하는 프로그램을 작성합시다.

반딧불이 timer 1s memory 128MB

반딧불이 1s 128MB