問題文

ALGO 街道は、全長 L キロメートルの直線状の道路です。街道の一方の端をスタート地点とし、もう一方の端をゴール地点とします。

この街道には N 個のガソリンスタンドがあります。i 個目 (1 \leq i \leq N) のガソリンスタンドはスタートから A_i キロメートルの地点にあり、価格は 1 リットル当たり C_i 円です。

燃費が 1 km/L であり、最大 K リットルのガソリンを貯めることができる車を利用したとき、スタートからゴールまで行くことが可能か判定し、もし可能ならば最小何円のガソリン代が必要かを求めるプログラムを求めてください。

ただし、最初の時点でガソリンは満タンであるとします。また、ガソリンの残量がちょうど 0 リットルになったときにガソリンスタンドで給油したり、ゴールに到達したりすることはできるものとします。

制約

• 0 \leq N \leq 700000
• 1 \leq K \leq L \leq 700000
• 1 \leq A_1 \leq A_2 \leq \dots \leq A_N \leq L - 1
• 1 \leq C_i \leq 10^{12}
• 入力はすべて整数

入力例 1

3 11 4
4 70
6 50
9 100

出力例 1

440

下図のように給油するのが最適です。ガソリンスタンド 1, 2, 3 でそれぞれ 2, 4, 1 リットルを給油するので、ガソリン代は 70 \times 2 + 50 \times 4 + 100 \times 1 = 440 円となります。

入力例 2

1 100 60
39 1

出力例 2

-1

たとえガソリンスタンド 1 で車のガソリンを満タンにしたとしても、スタートから 99 キロメートルの地点でガソリンが尽き、ゴールに到達することはできません。

入力例 3

6 100 30
19 1700000000
44 1400000000
44 1900000000
57 1600000000
78 1300000000
91 1500000000

出力例 3

100800000000