레프리콘의 황금
시간 제한2초메모리 제한1024 MB
일직선 위 금 항아리 n개를 한 번 순간 이동한 뒤 모으는 최단 시간과 순서를 구하는데, 그중 하나는 t분 뒤 사라집니다.
문제
아일랜드 출신 레프리콘 패트릭은 아내 클래리사와 크게 다툰 뒤, 급히 보라보라 섬으로 도망치려 한다. 패트릭에게는 한 직선 위에 숨겨 둔 개의 레프리콘 황금 단지가 있다. 다툼이 갑자기 일어나서 패트릭은 마법 부적과 護符를 충분히 챙기지 못했다. 그래서 그의 마법으로는 텔레포트를 한 번만 할 수 있지만, 어느 곳으로든 이동할 수 있다. 예를 들어 황금 단지가 있는 곳 중 하나로 이동할 수 있다. 이 텔레포트는 단지를 모으기 시작하기 전에 사용해야 한다.
레프리콘은 본래 잘 달리지 못하므로, 텔레포트가 없으면 패트릭은 1분에 1미터씩 이동한다. 그런데 클래리사가 단지 중 하나에 소멸 마법을 걸어서, 그 단지는 분 후에 사라진다. 패트릭이 모든 황금 단지를 가능한 한 짧은 시간에 모으도록 도와주자. 단지 하나라도 놓치면 여행에 필요한 황금이 부족해진다.
입력
첫 줄에는 황금 단지의 개수 과, 그중 하나가 사라지는 시간(분) 가 주어진다 (). 다음 줄에는 단지의 좌표(미터)가 개 주어진다. 모든 수는 서로 다르고, 절댓값은 100을 넘지 않는다. 좌표는 오름차순으로 주어진다. 마지막 줄에는 분 후에 사라질 단지의 번호가 주어진다.
출력
첫 줄에는 패트릭이 모든 황금을 모으는 데 걸리는 최소 시간을 출력한다. 다음 줄에는 단지를 모을 순서를 개의 수로 출력한다.