시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 131 51 33 36.264%

문제

기섭이는 여자친구와 여행을 하기 위해 운전면허를 따고 새 차를 샀다. 하지만, 그녀한테 차였다. 우울한 기섭이는 기분을 풀기 위해 드라이브를 나가려고 한다.

기섭이의 집에서 드라이브 목적지까지 총 거리를 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을 출력한다.

제한

  • 1 ≤ D ≤ 10,000 1 ≤ S1, S2, …, S≤ 10,000
  • 1 ≤ C, E ≤ 500, 0 ≤ N ≤ 1,000, 1 ≤ P1, P2, …, PN ≤ 10,000

예제 입력 1

10 2 10
3
3 4 2
2 3 1

예제 출력 1

20

예제 입력 2

20 2 40
4
2 5 3 2
20 10 15 10

예제 출력 2

-1

출처

University > 홍익대학교 > 2018 홍익대학교 컴퓨터공학과 코딩대회 F번

  • 문제의 오타를 찾은 사람: jh05013
  • 잘못된 데이터를 찾은 사람: jh05013
  • 문제를 만든 사람: loyong