問題文

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

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

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

IOI 君がジャンプして進んだ地点にチューターの家がある場合，IOI 君はその家に 1 回だけ泊まることができる．i 番目のチューターの家に泊まったとき，IOI 君の体力は B_{i} 増える．

IOI 君は，なるべく体力が大きい状態で M 前理事長の家に着きたい．

課題

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

制約

すべての入力データは以下の条件を満たす．

• 1 \leqq D \leqq 1\,000\,000\,000．
• 1 \leqq A \leqq 1\,000\,000\,000．
• 1 \leqq N \leqq 100\,000．
• 0 \leqq K < T_{1} < \cdot \cdot \cdot < T_{N} < M \leqq 1\,000\,000\,000．
• 1 \leqq B_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

小課題 1 [20 点]

• N \leqq 1\,000 を満たす．

小課題 2 [30 点]

• D \leqq 100 を満たす．

小課題 3 [50 点]

追加の制限はない．

入出力例

入力例 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 となる．