코알라
시간 제한2초메모리 제한256 MB
직선 도로 위 집들의 좌표, 최대 점프 거리, 점프당 체력 소모가 주어질 때 각 집을 한 번씩만 이용해 도착 지점에서 얻을 수 있는 최대 체력을 구한다.
문제
길쭉한 직선 도로 위에 JOI의 K 이사장 집과 M 전 이사장 집이 있다. 점프를 잘하는 코알라 IOI는 K 이사장 집에서 M 전 이사장 집으로 가는 계획을 세우고 있다.
이 도로는 수직선으로 볼 수 있고, 각 지점은 정수 좌표로 나타낸다. K 이사장 집의 좌표는 K이고, M 전 이사장 집의 좌표는 M이다. 두 집 사이에는 N개의 JOI 튜터 집이 있고, i번째 튜터 집의 좌표는 Ti이다.
IOI는 체력 0으로 K 이사장 집을 출발해 점프를 여러 번 반복해서 M 전 이사장 집으로 간다. 점프 한 번으로 M 전 이사장 집 방향으로 거리 d만큼 이동할 수 있다. 여기서 d는 1 ≤ d ≤ D를 만족하는 정수여야 한다. 점프를 한 번 하면 IOI의 체력은 A만큼 줄어든다. 체력은 음수가 될 수도 있다.
IOI가 점프해서 도착한 지점에 튜터 집이 있으면, IOI는 그 집에서 한 번만 잘 수 있다. i번째 튜터 집에서 잤을 때 IOI의 체력은 Bi만큼 늘어난다. IOI는 최대한 체력이 큰 상태로 M 전 이사장 집에 도착하고 싶어 한다.
코알라 IOI가 M 전 이사장 집에 도착했을 때의 체력으로 가능한 최댓값을 구하는 프로그램을 작성하시오.
입력
표준 입력에서 다음 입력을 읽는다.
- 첫째 줄에는 정수 K, M, D, A, N이 공백으로 구분되어 주어지며, 각각 K 이사장 집의 좌표, M 전 이사장 집의 좌표, 한 번에 점프할 수 있는 거리의 최댓값, 점프 한 번으로 줄어드는 체력, 튜터 집의 개수를 나타낸다.
- 이어지는 N개 줄 중 i번째 줄(1 ≤ i ≤ N)에는 두 정수 Ti, Bi가 공백으로 구분되어 주어지며, 각각 i번째 튜터 집의 좌표, i번째 튜터 집에서 잤을 때 늘어나는 체력을 나타낸다.
출력
표준 출력에 코알라 IOI가 M 전 이사장 집에 도착했을 때의 체력으로 가능한 최댓값을 나타내는 정수를 한 줄로 출력한다.
제한
- 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).