Informatica Online Judge

  운송용 헬기 [0206 / 00CE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 88   Total Tried : 630


The Champion of this Problem (C++) : gs17113 - ms / 608byte
My Best Submission (C++) : N/A

[]

Background

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

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

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

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

우리의 목적은 경유지에서 연료를 넣는 시간을 최소화 하면서 물건을 운송할 수 있는 방법을 결정하는 것이다. (출발점은 연료가 최대로 주유된 상태임.)

만약 연료를 넣는 시간을 최소화하는 방법이 여러 가지 있다면 그 중 경유지의 개수를 최소화해야 한다.

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





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

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

Input

첫째 줄에는 주유를 하지 않고 갈 수 있는 최대 거리 l이 주어진다. (l <= 1000)

둘째 줄에는 경유지의 수 n이 입력된다. (n <= 100)

셋째 줄에는 인접한 경유지 사이의 거리(km)가 차례로 주어진다. i번째 정수는 i-1번째 경유지와 i번째 경유지간의 거리를 의미하며, 1000 이하의 양의 정수이다.

넷째 줄에는 경유지별 주유 시간(분)이 차례로 주어진다. 시간은 1000 이하의 양의 정수이다.

Output

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

IO Example

입력
140
5
60 50 40 100 30 100
7 11 4 10 5

출력
16 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]