헬기로 출발지에서 목적지까지 원하는 짐을 운송하려고 한다.

하지만 거리에 따라 필요한 경우 경유지에 들러서 연료를 보충해야 한다.

경유지들은 출발지에서 도착지로 가는 경로에 있으며 1번부터 차례로 번호가 붙어 있다.

이 헬기는 한 번의 연료 보급으로 최대로 갈 수 있는 거리와 경유지마다 연료를 보충하는데 걸리는 시간이 정해져 있다.

우리의 목적은 경유지에서 연료를 넣는 시간을 최소화 하면서 물건을 운송할 수 있는 방법을 결정하는 것이다.

이를 해결할 수 있는 프로그램을 작성하시오.(출발점은 연료가 최대로 주유된 상태임.)

예를 들어, 아래의 그림과 같이 경유지가 5개 있고, 한 번 주유를 하면 최대 140km를 갈 수 있는 경우를 생각해 보자.

헬기가 출발지에서 경유지 1, 3, 5번을 차례로 방문하여 도착지까지 갈 수도 있고, 경유지 2, 4번을 방문하여 갈 수도 있다.

이 때 1, 3, 5번을 방문하는 경우에는 16분(7+4+5)이 걸리는데 2, 4번을 방문하게 되면 21분(11+10)이 걸리게 되므로 1, 3, 5번을 방문하는 것이 주유 시간을 최소화 하게 된다.

첫째 줄에는 주유를 하지 않고 갈 수 있는 최대 거리가 주어진다. 둘째 줄에는 경유지의 수가 입력되는데 경유지의 수는 100이하이다.

셋째 줄에는 인접한 경유지 사이의 거리(km)가 차례로 주어진다. 넷째 줄에는 경유지별 주유 시간(분)이 차례로 주어진다. 모든 입력은 양의 정수이다.

출력내용은 경유지에서 주유하는데 걸리는 총 주유 시간(분)과 방문한 경유지의 수를 출력한다.