JOI Spring Camp 2017 Day 3 #1- Long Distance Coach > 문제은행 : 정보올림피아드&알고리즘


4686 : Long Distance Coach

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

도시 I와 도시 O 사이를 이동하는 고속버스가 있다.

버스에는 정수기가 있어, 승객과 운전사가 물을 마실 수 있다.

버스는 0초에 도시 I에서 출발해서, X초에 도시 O에 도착한다.

경로에는 N개의 리필 구역이 있어 정수기에 물을 다시 채울 수 있다.

버스는 i번째 리필 구역(1 ≤ i ≤ N)을 Si초에 지날 것이다.

 

시작할 때, 정수기에는 물이 들어있지 않다.

출발 전에 정수기에 물을 채울 수 있다.

또한, 버스가 리필 구역에 있을 때도 정수기에 물을 채울 수 있다.

물의 비용은 버스의 위치에 상관없이 리터당 W원이다.

 

도시 I에서, M명의 승객이 버스에 탑승한다.

승객은 1번부터 M번까지 번호가 붙여져 있다.

어떤 승객도 도시 I 이외의 곳에서 버스에 탑승하지 않는다.

 

j번 승객(1 ≤ j ≤ M)은 Dj초부터 시작해서 T초마다 물 1리터를 마셔야 한다.

다른 말로, j번 승객은 Dj + kT(k = 0, 1, 2, ...)초에 물을 마셔야 한다.

1 ≤ Dj < T을 만족하며, 모든 승객에 대하여 T의 값은 동일하다.

승객이 물을 마셔야 할 때 정수기에 물이 들어있지 않다면 승객은 버스에서 내린다.

j번 승객이 도시 O에 도착하기 전에 버스에서 내린다면 Cj원을 환불해 주어야 한다.

 

운전자 또한 물을 마셔야 한다.

운전자는 0초부터 시작해서 T초마다 물 1리터를 마셔야 한다.

다른 말로, 운전자는 kT(k = 0, 1, 2, ...)초에 물을 마셔야 한다.

운전자가 물을 마셔야 할 때 정수기에 물이 들어있지 않다면 버스의 운행은 멈춘다.

 

같은 시간에 서로 다른 두 명의 사람이 물을 마시는 일은 없음이 보장된다.

또한, 버스가 도시 O나 리필 구역에 도착하는 순간에 물을 마셔야 하는 사람은 없음이 보장된다.

 

각 리필 구역에서 정수기에 넣을 물의 양을 조절함으로서 도시 O까지 버스를 운행시키면서, 동시에 물에 대한 비용과 환불 금액의 합을 최소화시키고 싶다.

당신은 어디서 얼만큼 정수기에 물을 넣어야 하는지를 정해야 한다.

 

버스의 운행 시간, 리필 구역의 정보, 승객과 운전자의 정보가 주어진다.

버스가 도시 O까지 운행할 때 물에 대한 비용과 환불 금액의 합의 최솟값을 구하여라.​ 


입력형식

1번 줄 : X N M W T

2번 ~ N + 1번 줄 : Si

N + 2번 줄 ~ N + M + 1번 : Dj Cj

 

- 1 ≤ X ≤ 1 000 000 000 000

- 1 ≤ N ≤ 200 000

- 1 ≤ M ≤ 200 000

- 1 ≤ W ≤ 1 000 000

- 1 ≤ T ≤ X

- 1 ≤ Si < X (1 ≤ i ≤ N)

- 1 ≤ Dj < T (1 ≤ j ≤ M)

- 1 ≤ Cj ≤ 1 000 000 000 (1 ≤ j ≤ M)

- Dj (1 ≤ j ≤ M)은 서로 다르다.

- 버스가 도시 O나 리필 구역에 도착했을 때, 운전자나 승객들은 물을 필요로 하지 않는다.​ 


출력형식

첫 번째 줄에 최소 비용을 출력하여라.


입력 예

19 1 4 8 7
10
1 20
2 10
4 5
6 5

출력 예

103


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP