만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

레프리콘의 황금

시간 제한2초메모리 제한1024 MB

요약
일직선 위 금 항아리 n개를 한 번 순간 이동한 뒤 모으는 최단 시간과 순서를 구하는데, 그중 하나는 t분 뒤 사라집니다.
난이도

보통10점 중 5점

유형
완전 탐색, 그리디, 구현
정답자
아직 제출이 없습니다

문제

아일랜드 출신 레프리콘 패트릭은 아내 클래리사와 크게 다툰 뒤, 급히 보라보라 섬으로 도망치려 한다. 패트릭에게는 한 직선 위에 숨겨 둔 nn개의 레프리콘 황금 단지가 있다. 다툼이 갑자기 일어나서 패트릭은 마법 부적과 護符를 충분히 챙기지 못했다. 그래서 그의 마법으로는 텔레포트를 한 번만 할 수 있지만, 어느 곳으로든 이동할 수 있다. 예를 들어 황금 단지가 있는 곳 중 하나로 이동할 수 있다. 이 텔레포트는 단지를 모으기 시작하기 전에 사용해야 한다.

레프리콘은 본래 잘 달리지 못하므로, 텔레포트가 없으면 패트릭은 1분에 1미터씩 이동한다. 그런데 클래리사가 단지 중 하나에 소멸 마법을 걸어서, 그 단지는 tt분 후에 사라진다. 패트릭이 모든 황금 단지를 가능한 한 짧은 시간에 모으도록 도와주자. 단지 하나라도 놓치면 여행에 필요한 황금이 부족해진다.

입력

첫 줄에는 황금 단지의 개수 nn과, 그중 하나가 사라지는 시간(분) tt가 주어진다 (2≤n,t≤1002 \le n, t \le 100). 다음 줄에는 단지의 좌표(미터)가 nn개 주어진다. 모든 수는 서로 다르고, 절댓값은 100을 넘지 않는다. 좌표는 오름차순으로 주어진다. 마지막 줄에는 tt분 후에 사라질 단지의 번호가 주어진다.

출력

첫 줄에는 패트릭이 모든 황금을 모으는 데 걸리는 최소 시간을 출력한다. 다음 줄에는 단지를 모을 순서를 nn개의 수로 출력한다.

예제2

  1. 예제 1

    입력
    5 5
    1 4 9 16 25
    2
    
    예상 출력
    24
    1 2 3 4 5 
    
  2. 예제 2

    입력
    6 4
    1 2 3 6 8 25
    5
    
    예상 출력
    31
    5 4 3 2 1 6