시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 460 | 140 | 109 | 29.459% |
기섭이는 여자친구와 여행을 하기 위해 운전면허를 따고 새 차를 샀다. 하지만, 그녀한테 차였다. 우울한 기섭이는 기분을 풀기 위해 드라이브를 나가려고 한다.
기섭이의 집에서 드라이브 목적지까지 총 거리를 D km라고 하자. 기섭이가 산 차량은 연료 용량이 C 리터이고, 연비가 E (L/1 km) 로 정해져 있어, 집에서 목적지까지 한 번에 도달하지 못 할 수 있다. 다행히 목적지와 집 사이에는 각 주유소마다 S1, S2, …, SN(km) 거리만큼 떨어진 N개의 주유소가 존재한다.(단, S1은 첫 번째 주유소와 집 사이의 거리). 각 주유소에서 파는 기름의 가격은 주유소마다 다를 수 있다.
차를 사느라 돈을 많이 쓴 기섭이는 최소한의 비용으로 목적지까지 가려고 한다. 기섭이를 위해 목적지까지 가기 위한 최소비용을 구해주자.
기섭이가 집에서 출발할 때 연료는 가득 차 있다고 한다.
첫 번째 줄에 차량의 최대 연료 용량 C, 차량이 1km가는 동안 사용하는 기름의 양 E, 목적지까지의 거리 D가 주어진다.
두 번째 줄에는 주유소의 개수 N이 주어진다. N=0이면 더 이상의 입력이 주어지지 않는다.
세 번째 줄에는 각 주유소 간의 거리(S1, S2, …, SN)가 공백 하나를 사이에 두고 주어진다.
네 번째 줄에는 첫 번째 주유소부터 N번째 주유소까지 기름의 리터당 가격(P1, P2, …, PN)이 공백 하나를 사이에 두고 순서대로 주어진다.
목적지까지 가는데 필요한 기름값의 최소비용을 출력한다.
만약 도착할 수 없을 경우 -1을 출력한다.
10 2 10 3 3 4 2 2 3 1
20
20 2 40 4 2 5 3 2 20 10 15 10
-1