자동차 경주 대회

전국 자동차 경주 대회가 매년 열린다. 출발지점에서 도착지점까지의 거리가 매우 멀기 때문에, 경주 도중 자동차는 길가에 있는 정비소에서 정비를 받을 수 있다. 정비소는 출발지점에서 도착지점 방향으로 1번부터 차례대로 번호가 붙어 있다.

경기 규칙상 자동차는 정비를 받은 뒤 미리 정해진 최대 거리보다 더 멀리 달릴 수 없다. 각 정비소에서 정비하는 데 걸리는 시간은 서로 다를 수 있다.

출발지점에서 도착지점까지 규칙을 지키며 이동할 때, 정비소에서 쓰는 총 정비 시간이 최소가 되도록 방문할 정비소를 정해야 한다. 최소 총 정비 시간과 방문할 정비소 번호를 구하는 프로그램을 작성하시오.

예를 들어 정비소가 5개 있고 한 번 정비를 받은 뒤 최대 140km를 갈 수 있다고 하자. 출발지점에서 1번 정비소까지의 거리가 100km이고, 1번 정비소의 정비 시간은 5분이다. 이때 1번, 3번, 5번 정비소를 방문하면 총 16분이 걸리고, 2번, 4번 정비소를 방문하면 총 21분이 걸리므로 전자가 더 좋다.

첫째 줄에 정비를 받지 않고 갈 수 있는 최대 거리가 주어진다.

둘째 줄에 정비소의 개수 n이 주어진다. 정비소의 수는 100개 이하이다.

셋째 줄에 출발지점, 정비소들, 도착지점을 잇는 인접 구간의 거리가 차례대로 주어진다. 즉, 총 n + 1개의 거리가 주어진다. 각 거리는 최대 거리 이하이고, 모든 거리의 합은 2^31 - 1 이하이다.

넷째 줄에 1번 정비소부터 n번 정비소까지의 정비 시간이 차례대로 주어진다. 모든 정비 시간의 합은 2^31 - 1 이하이다.

모든 입력 값은 양의 정수이며 2^31 - 1 이하이다.

첫째 줄에 정비소에서 쓰는 최소 총 정비 시간을 출력한다.

둘째 줄에 방문하는 정비소의 개수를 출력한다.

방문하는 정비소가 있다면 셋째 줄에 방문하는 정비소 번호를 이동 순서대로 출력하고, 번호 사이에는 공백을 하나씩 둔다.

방문할 정비소가 없다면 총 정비 시간은 0이며, 정비소 번호 줄은 출력하지 않는다.