Informatica Online Judge

  메뚜기와 배짱이 [1213 / 04BD]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI 2013 Spring Camp]

Background

GSHS는 하나의 수직선으로 이루어진 나라이다.

이 나라에는 경곽이의 집과 영재의 집이 있다.

점프하는 것이 특기인 JK메뚜기는 경곽이의 집으로부터 영재의 집으로 가는 방법에 대해 계획을 세우고 있다.

이 나라의 모든 위치는 정수로 이루어진 좌표로 되어 있고, 경곽이의 집은 k, 영재의 집은 m의 위치에 있다.

이 두 집 사이에는 N개의 배짱이 집이 있으며, i번째 배짱이의 집은 T_i에 위치한다.

JK메뚜기는 체력이 0으로 경곽이의 집에서 출발하고, 점프를 몇 번 하여 영재의 집으로 간다.

1번 점프하여, 영재의 집방향으로 거리 d만큼 이동할 수 있다.

여기서 d는 1 <= d <= D를 만족하며, 자연수값이다.

한 번 점프를 한 메뚜기는 체력이 A만큼 감소한다. (체력은 음수가 될 수도 있다.)

JK메뚜기가 점프하여 도착한 지점이 배짱이의 집일 경우에는 그 집에서 쉬어갈 수 있다. i번째 배짱이의 집에서 쉴 경우, JK메뚜기의 체력은 B_i만큼 회복된다.

JK메뚜기는 가능한 한 체력 값이 큰 상태에서 영재의 집에 도착하고자 한다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 정수 k, m, D, A, N의 값이 공백으로 구분되어 입력된다.

두 번째줄부터 N줄에 걸쳐서 각 배짱이들의 집의 위치인 T_i와 회복양을 의미하는 B_i의 값이 공백으로 구분되어 입력된다.

[입력값의 정의역]
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 )

[Sub-Task Info]
#1 : N <= 1,000 (20%)
#2 : D <= 100 (30%)
#3 : 추가제한사항없음(50%)

Output

JK메뚜기가 영재의 집에 도착했을 때의 최대 체력을 출력한다.

IO Example

입력
0 10 4 10 2
3 10
8 5

출력
-20

* 설명 :

JK메뚜기가 다음과 같이 이동할 경우 최적이 된다.

- 거리 3을 점프한다. JK는 위치 3에 도착하고 체력은 -10이된다.
- 첫 번째 배짱이의 집에서 체력을 10회복하여 체력은 0이된다.
- 다음으로 거리 4를 점프한다. 위치 7에 도착하고 체력은 -10.
- 마지막으로 거리 3을 점프하여 위치 m인 영재의 집에 도착하고 체력은 -20이된다.

이보다 더 많은 체력을 가지고 영재의 집에 도착할 수 있는 방법은 없다.

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