페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5022
서브태스크

점프 2000초 256MB

문제

당신은 수직선 위에 서있다.

당신의 현재 위치는 K이고 몇 번의 점프를 통해 정확히 M으로 이동하는 것이 목적이다. (K < M)

만약 x에서 점프를 한다면 x+d 로 이동할 수 있다. (1 <= d <= D)

당신이 한 번의 점프를 실행할 때마다 A만큼의 에너지를 잃으며 에너지는 음수일 수 있다.

수직선 위에는 위치에 도달했을 때 에너지를 얻을 수 있는 N개의 지점이 있다.

i번째 지점의 위치는 T_i 이고 T_i 에 위치하게 되면 당신은 B_i의 에너지를 얻는다.

당신은 M에 도착할 때 가능한 최대의 에너지를​​ 가지고 있도록 이동하고 싶다.

규칙대로 점프를 하며 적절히 움직일 때 도착시 보유할 수 있는 최대 에너지는 얼마일까?


입력

다음의 순서대로 입력이 주어진다.

K M D A N

T_1 B_1

...

T_N B_N

 

<제한>

1 ≤ D ≤ 1,000,000,000

1 ≤ A ≤ 1,000,000,000

1 ≤ N ≤ 100,000

0 ≤ K < T_1 < · · · < T_N < M ≤ 1,000,000,000

1 ≤​ B_i ≤ 1,000,000,000 (1 ≤​ i ≤ N)​ 


출력

규칙대로 점프를 하며 적절히 움직일 때 도착 시 보유할 수 있는 최대 에너지​를 출력하라.


부분문제

번호 점수 조건
#120점

N <= 1,000

#230점

D <= 100

#350점

추가적인 제한 조건 없음. 


예제1

입력
0104102

310

85
출력
-20

예제2

입력
3429108

105

129

267

272

308

346

368

4010
출력
-25

출처

JOI spring camp 2013

역링크 공식 문제집만