시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2 2 2 100.000%

문제

細長い直線状の道に JOI の K 理事長の家と M 前理事長の家がある.ジャンプが得意であるコアラの IOI 君は,K 理事長の家から M 前理事長の家に行く計画を立てている.

この道は数直線と見なされ,各地点は 1 個の数による座標で表される.K 理事長の家の座標は K であり, M 前理事長の家の座標は M である.これらの間には N 個の JOI チューターの家があり,i 番目のチューター の家の座標は Ti である.

IOI 君は体力 0 で K 理事長の家を出発し,ジャンプを何回か繰り返して M 前理事長の家に行く.1 回 のジャンプによって,M 前理事長の家の方向に距離 d 進んだ位置に移動することができる.ここで,d は 1 ≤ d ≤ D を満たす整数でなければならない.1 回のジャンプを行うと,IOI 君の体力は A 減る (体力は負 の値にもなりうる).

IOI 君がジャンプして進んだ地点にチューターの家がある場合,IOI 君はその家に 1 回だけ泊まることが できる.i 番目のチューターの家に泊まったとき,IOI 君の体力は Bi 増える. IOI 君は,なるべく体力が大きい状態で M 前理事長の家に着きたい.

コアラの IOI 君が M 前理事長の家に着いたときの体力の値として考えられる最大値を求めるプログラム を作成せよ.

입력

標準入力から以下の入力を読み込め.

  • 1 行目には整数 K, M, D, A, N が空白を区切りとして書かれており,それぞれ K 理事長の家の座標,M 前理事長の家の座標,1 回でジャンプできる距離の最大値,1 回のジャンプで減る体力,チューター の家の個数を表す.
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には 2 個の整数 Ti, Bi が空白を区切りとして書かれており,そ れぞれ i 番目のチューターの家の座標,i 番目のチューターの家に泊まったときに増える体力を表す.

출력

標準出力に,コアラの IOI 君が M 前理事長の家に着いたときの体力の値として考えられる最大値を表す 整数を 1 行で出力せよ.

제한

  • 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

0 10 4 10 2
3 10
8 5

예제 출력 1

-20

この例では,IOI 君は例えば以下のように行動するのが最適である.

  • 距離 3 のジャンプを行う.IOI 君は座標 3 の位置に着き,体力は −10 となる.
  • 1 番目のチューターの家に泊まる.体力は 0 となる.
  • 距離 4 のジャンプを行う.IOI 君は座標 7 の位置に着き,体力は −10 となる.
  • 距離 3 のジャンプを行う.IOI 君は M 前理事長の家に着き,体力は −20 となる.

예제 입력 2

3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10

예제 출력 2

-25

この例では,IOI 君は例えば以下のように行動するのが最適である.

  • 距離 9 のジャンプを行う.IOI 君は座標 12 の位置に着き,体力は −10 となる.
  • 2 番目のチューターの家に泊まる.体力は −1 となる.
  • 距離 9 のジャンプを行う.IOI 君は座標 21 の位置に着き,体力は −11 となる.
  • 距離 9 のジャンプを行う.IOI 君は座標 30 の位置に着き,体力は −21 となる.
  • 5 番目のチューターの家に泊まる.体力は −13 となる.
  • 距離 6 のジャンプを行う.IOI 君は座標 36 の位置に着き,体力は −23 となる.
  • 7 番目のチューターの家に泊まる.体力は −15 となる.
  • 距離 6 のジャンプを行う.IOI 君は M 前理事長の家に着き,体力は −25 となる.