0657 - 長距離バス (Long Distance Coach)

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / Writer root / x 0 / 統計 /

TLE
2sec
MLE
256MB
得点
100

IOI 国には都市 I と都市 O を結ぶ長距離バスが走っている．バスの車内には給水器が設置されており，乗客や運転手は水を飲むことができる．バスは時刻 0 に都市 I を出発し，時刻 X に都市 O に到着する．途中には，水を補給できる地点が N 個ある．バスが i 番目 (1 ≤ i ≤ N) の補給地点を訪れる時刻は Si である．

最初，給水器には水は入っていない．バスの出発前に水を補給することができる．また，補給地点においても水を補給することができる．水を補給するコストは，場所によらず，1 リットルあたり W 円である．

このバスには都市 I で M 人の乗客が乗車し，乗客には 1 から M の番号が付けられている．都市 I 以外の場所では，新たな乗客が乗車することはない．乗客 j (1 ≤ j ≤ M) は時刻 Dj に 1 リットルの水を必要とする．また，水を必要としてから時間 T が経過する度に，再び 1 リットルの水を必要とする．すなわち，乗客 j が水を必要とするのは，時刻 Dj + kT (k = 0, 1, 2, ...) においてである．ここで，1 ≤ Dj < T であり，T の値は乗客によらず一定である．乗客が水を必要としたときに給水器に水が残っていないと，その乗客は途中下車してしまう．乗客 j が都市 O に到着する前に途中下車した場合，運賃の払い戻しとして Cj 円のコストがかかる．

運転手も水を必要とする．運転手は時刻 0 に 1 リットルの水を必要とし，乗客と同様，水を必要としてから時間 T が経過する度に，再び 1 リットルの水を必要とする．すなわち，運転手が水を必要とするのは，時刻 kT (k = 0, 1, 2, ...) においてである．運転手が水を必要としたときに給水器に水が残っていないと，バスの運行を続けることができない．

2 人以上の人が同時に水を必要とすることはない．また，バスが都市 O や補給地点を訪れると同時に，乗客や運転手が水を必要とすることはない．

補給地点における水の補給量を調整することで，水の補給にかかるコストと，運賃の払い戻しにかかるコストの合計を小さくして，バスを都市 O まで運行したい．あなたの仕事は，バスの運行中に，どの地点でどれだけ水を補給するかを決定することである．

課題

バスの運行にかかる時間，補給地点の情報，乗客および運転手の情報が与えられたとき，バスを都市 O まで運行するための，水の補給にかかるコストと，運賃の払い戻しにかかるコストの合計の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

  • 1 行目には，5 個の整数 X, N, M, W, T が空白を区切りとして書かれている．これは，バスが時刻 X に都市 O に到着し，補給地点が N 個あり，バスに乗客が M 人いて，水 1 リットルの補給にかかるコストが W 円であって，乗客や運転手が水を必要とする間隔が T であることを表す．
  • 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 Si が書かれている．これは，バスが i 番目の補給地点を訪れるのが時刻 Si であることを表す．
  • 続く M 行のうちの j 行目 (1 ≤ j ≤ M) には，2 個の整数 Dj, Cj が空白を区切りとして書かれている．これは，乗客 j が最初に水を必要とする時刻が Dj であることと，乗客 j が途中下車した場合のコストが Cj 円であることを表す．

出力

標準出力に，必要なコストの合計の最小値を表す整数を 1 行で出力せよ．

制限

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

  • 1 ≤ X ≤ 1 000 000 000 000．
  • 1 ≤ N ≤ 200 000．
  • 1 ≤ M ≤ 200 000．
  • 1 ≤ W ≤ 1 000 000．
  • 1 ≤ T ≤ X．
  • 1 ≤ Si < X (1 ≤ i ≤ N)．
  • 1 ≤ Dj < T (1 ≤ j ≤ M)．
  • 1 ≤ Cj ≤ 1 000 000 000 (1 ≤ j ≤ M)．
  • Dj (1 ≤ j ≤ M) は互いに異なる．
  • バスが都市 O や補給地点を訪れると同時に乗客や運転手が水を必要とすることはない．

小課題

この課題では小課題は全部で 4 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題 1 [16 点]

  • N ≤ 8．
  • M ≤ 8．

小課題 2 [30 点]

  • N ≤ 100．
  • M ≤ 100．

小課題 3 [25 点]

  • N ≤ 2 000．
  • M ≤ 2 000．

小課題 4 [29 点]

追加の制限はない．

入出力例

入力例 1

19 1 4 8 7
10
1 20
2 10
4 5
6 5

出力例 1

103

この入力例において，出発前に 7 リットル，1 番目の補給地点で 4 リットルの水を補給する場合，バスの運行は次のように行われる．

  1. バスが都市 I を出発する．この時点で給水器には 7 リットルの水が入っている．
  2. 運転手および乗客 1, 2, 3, 4 がそれぞれ時刻 0, 1, 2, 4, 6 に水を 1 リットルずつ飲み，残りの水量は 2 リットルになる．
  3. 運転手および乗客 1 がそれぞれ時刻 7, 8 に再び水を 1 リットルずつ飲み，残りの水量は 0 リットルになる．
  4. 時刻 9 に乗客 2 が水を必要とするが，給水器に水が無いので途中下車する．
  5. 時刻 10 に 1 番目の補給地点で水を 4 リットル補給する．残りの水量は 4 リットルになる．
  6. 乗客 3, 4，運転手，および乗客 1 がそれぞれ時刻 11, 13, 14, 15 に水を 1 リットルずつ飲み，残りの水量は 0 リットルになる．
  7. 時刻 18 に乗客 3 が水を必要とするが，給水器に水が無いので途中下車する．
  8. 時刻 19 にバスが都市 O に到着する．

水の補給は計 11 リットル行われるため給水にかかるコストは 88 円である．乗客 2, 3 が途中下車するコストは合計で 15 円である．これらの合計は 103 円である．

102 円以下の合計コストでバスを最後まで運行することはできないので，103 を出力する．

入力例 2

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

出力例 2

547

入力例 3

1000000000000 1 1 1000000 6
999999259244
1 123456789

出力例 3

333333209997456789