코알라 Batch 컴파일 명령

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

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

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

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

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

해야 할 일

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

입력 형식

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

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

출력 형식

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

제약 조건

• 1 ≤ D ≤ 1 000 000 000
• 1 ≤ A ≤ 1 000 000 000
• 1 ≤ N ≤ 100 000
• 0 ≤ K < T₁ < ... < T_N < M ≤ 1 000 000 000
• 1 ≤ B_i ≤ 1 000 000 000(1 ≤ i ≤ N)

부분문제

부분문제 1 [20점]

• N ≤ 1 000

부분문제 2 [30점]

• D ≤ 100

부분문제 3 [50점]

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

예제

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

• 거리가 3인 점프를 합니다. 우현이는 좌표가 3인 지점으로 가고 체력은 -10이 됩니다.
• 1번 간이 숙소에 묵습니다. 체력은 0이 됩니다.
• 거리가 4인 점프를 합니다. 우현이는 좌표가 7인 지점으로 가고 체력은 -10이 됩니다.
• 거리가 3인 점프를 합니다. 우현이는 석환이의 집에 도착하고 체력은 -20이 됩니다.

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

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