Background

你这前面的题太难了，要返璞归真一下。

Description

你有一个可以无限装油的车，你要开这个车进行旅游。

将旅游路线抽象为数轴。路上有 $n$ 个加油站，每个加油站都可以无限加油。从左到右第 $i$ 个加油站位于位置 $p_i\,(p_i\geq 0)$，每加一升油需要 $a_i$ 元，对于每次加油，加油量须为整数。一升油可以让你的车行进 $D$ 单位长度的距离。

你从第一个加油站的位置出发，初始时没有任何油。你需要到位置 $S\,(S\geq p_n)$. 你需要求出整趟旅行加油所耗的钱的最小值。

Format

Input

第一行三个整数 $n,S,D\,(1\leq n\leq 10^5,0\leq S\leq 10^9,1\leq D\leq 10^9)$.

随后 $n$ 行，每行两个整数 $p_i,a_i\,(0\leq p_i,a_i\leq 10^9,\,\forall 1\leq i < n,p_i\leq p_{i+1})$.

Output

仅一个整数表示最小总花费。

Samples

1 115 1
114 514

514

5 40 4
0 9
10 8
20 9
30 6
40 5

79

Limitation

1s, 256MiB.