문제 보기 - 코알라 (JOI13_koala)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
2000 ms 256 MiB 127 44 34.65%

긴 직선 모양의 길 위에 지학이의 집과 석환이의 집이 있습니다. 점프가 특기인 코알라 우현이는 지학이의 집에서 출발하여 석환이의 집에 가려고 합니다.

이 길 위의 각 지점은, 1개의 수로 표현되는 좌표로 나타낼 수 있습니다. 지학이의 집의 좌표는 K이고, 석환이의 집의 좌표는 M입니다. 이 두 집 사이에는 N개의 간이 숙소가 있습니다. i번째 간이 숙소의 좌표는 Ti입니다.

우현이는 체력이 0인 상태로 지학이의 집을 떠나서, 점프를 몇 차례 반복하여, 석환이의 집에 갑니다. 한 번 점프하면, 우현이는 석환이의 집 쪽으로 d만큼 이동한 위치로 이동할 수 있습니다. 이 때 d1 ≤ d ≤ D를 만족하는 정수여야 합니다. 한 번 점프하면, 우현이의 체력은 A만큼 줄어듭니다. 체력의 값은 음수가 될 수도 있습니다.

우현이가 뛰어서 도착한 지점에 간이 숙소가 있다면, 우현이는 그 곳에서 최대 1회까지 잘 수 있습니다. 우현이가 i번째 간이 숙소에 묵으면, 체력의 값이 Bi만큼 증가합니다.

우현이는 가급적 체력이 많은 (체력의 값이 큰) 상태로 석환이의 집에 도착하고자 합니다.

해야 할 일

우현이가 적절히 점프하여 석환이의 집에 도착했을 때 우현이의 체력의 값의 최댓값을 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 지학이의 집의 좌표 K, 석환이의 집의 좌표 M, 한 번 점프할 수 있는 거리의 최댓값 D, 한 번 점프하면 줄어드는 체력 A, 간이 숙소의 개수 N이 공백을 사이로 두고 주어집니다. 이 수들은 모두 정수입니다.

이후 N개의 줄이 주어지는데, 이 중 i번째 줄 (1 ≤ i ≤ N)에는 i번째 간이 숙소의 좌표 Tii번째 간이 숙소에서 자면 늘어나는 체력 Bi가 공백을 사이로 두고 주어집니다. 이 수들은 모두 정수입니다.

출력 형식

첫 번째 줄에 우현이가 적절히 점프하여 석환이의 집에 도착했을 때 우현이의 체력의 값의 최댓값을 나타내는 정수 하나를 출력하세요.

제약 조건

  • 1 ≤ D ≤ 1 000 000 000
  • 1 ≤ A ≤ 1 000 000 000
  • 1 ≤ N ≤ 100 000
  • 0 ≤ K < T1 < ... < TN < M ≤ 1 000 000 000
  • 1 ≤ Bi ≤ 1 000 000 000(1 ≤ i ≤ N)

부분문제

부분문제 1 [20점]

  • N ≤ 1 000

부분문제 2 [30점]

  • D ≤ 100

부분문제 3 [50점]

추가 제약 조건이 없습니다.

예제

입력 예시 1 출력 예시 1
0 10 4 10 2
3 10
8 5
-20

이 예제에서, 다음과 같이 행동하는 것이 최적입니다.

  • 거리가 3인 점프를 합니다. 우현이는 좌표가 3인 지점으로 가고 체력은 -10이 됩니다.
  • 1번 간이 숙소에 묵습니다. 체력은 0이 됩니다.
  • 거리가 4인 점프를 합니다. 우현이는 좌표가 7인 지점으로 가고 체력은 -10이 됩니다.
  • 거리가 3인 점프를 합니다. 우현이는 석환이의 집에 도착하고 체력은 -20이 됩니다.
입력 예시 2 출력 예시 2
3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10
-25

이 예제에서, 다음과 같이 행동하는 것이 최적입니다.

  • 거리가 9인 점프를 합니다. 우현이는 좌표가 12인 지점으로 가고 체력은 -10이 됩니다.
  • 2번 간이 숙소에 묵습니다. 체력은 -1이 됩니다.
  • 거리가 9인 점프를 합니다. 우현이는 좌표가 21인 지점으로 가고 체력은 -11이 됩니다.
  • 거리가 9인 점프를 합니다. 우현이는 좌표가 30인 지점으로 가고 체력은 -21이 됩니다.
  • 5번 간이 숙소에 묵습니다. 체력은 -13이 됩니다.
  • 거리가 6인 점프를 합니다. 우현이는 좌표가 36인 지점으로 가고 체력은 -23이 됩니다.
  • 7번 간이 숙소에 묵습니다. 체력은 -15이 됩니다.
  • 거리가 6인 점프를 합니다. 우현이는 석환이의 집에 도착하고 체력은 -25가 됩니다.