Problem: Silver Fox is fighting with N monsters.

The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the health of H_i.

Silver Fox can use bombs to attack the monsters. Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A. There is no way other than bombs to decrease the monster's health.

Silver Fox wins when all the monsters' healths become 0 or below.

Find the minimum number of bombs needed to win.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 0 \leq D \leq 10^9
* 1 \leq A \leq 10^9
* 0 \leq X_i \leq 10^9
* 1 \leq H_i \leq 10^9
* X_i are distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N D A
X_1 H_1
:
X_N H_N


Output

Print the minimum number of bombs needed to win.

Examples

Input

3 3 2
1 2
5 4
9 2


Output

2


Input

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5


Output

5


Input

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000


Output

3000000000

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long d = sc.nextLong()*2;
        long a = sc.nextLong();
        long[][] x = new long[n][2];
        long[] b = new long[n];
        for (int i = 0; i < n; i++) {
            x[i][0] = sc.nextLong();
            x[i][1] = sc.nextLong();
            b[i] = x[i][0];
        }
        Arrays.sort(x, (s, t) -> Long.compare(s[0], t[0]));
        Arrays.sort(b);
        LazySegTree_RSQ seg = new LazySegTree_RSQ(n);
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            long rest = x[i][1] - seg.max(i, i+1, 0, 0, seg.size);
            if(rest < 1) continue;
            int num = (int) Math.ceil((double)rest / a);
            int r = Arrays.binarySearch(b, b[i]+d);
            if(r < 0) r = ~r -1;
            seg.add(i, r+1, num*(int)a, 0, 0, seg.size);
            ans += num;
        }
        System.out.println(ans);
        sc.close();

    }

}

class LazySegTree_RSQ {

    public int n;
    public int size;
    /**
     * 要素全体を含むノードのindex：0.
     * k番目(0-indexed)の要素のindex：k + size - 1
     * ノードkの親要素のindex：(k - 1) / 2.
     * ノードkの子要素のうち左側のindex：k*2+1.
     * ノードkの子要素のうち右側のindex：k*2+2.
     */
    public long[] data;
    public long[] lazy;

    /**
     * コンストラクタ.
     * @param n 要素数
     */
    public LazySegTree_RSQ(int n){
        this.n = n;
        size = 1;
        while(size < n) size *= 2;
        data = new long[size*2];
        lazy = new long[size*2];
    }

    /**
     * 指定したノードが遅延評価待ちの値を保持している場合、
     * 自ノードに反映し、子ノードの遅延評価待ちとして設定する。
     * @param k 自ノードのindex
     * @param l 自ノードの対象区間左側（含む）
     * @param r 自ノードの対象区間右側（含まない）
     */
    public void eval(int k, int l, int r){
        if(lazy[k] != 0){
            data[k] += lazy[k];
            if(1 < r - l){
                lazy[2*k+1]  += lazy[k] / 2;
                lazy[2*k+2]  += lazy[k] / 2;
            }
            lazy[k] = 0L;
        }
    }

    /**
     * 区間[a, b)での○○を求めます.
     * 最初に呼ぶ際は、query(a, b, x, 0, 0, size)として呼ぶ.
     * @param a 求める区間の下限（含む）
     * @param b 求める区間の上限（含まない）
     * @param k 確認するノードのindex
     * @param l 確認するノードの下限（含む）
     * @param r 確認するノードの上限（含まない）
     * @return 区間[a, b)での○○
     */
    public void add(int a, int b, int x, int k, int l, int r){
        eval(k, l, r);

        // 区間外
        if(b <= l || r <= a) return;

        // 完全に含む
        if(a <= l && r <= b){
            lazy[k] += (long)(r - l) * x;
            eval(k, l, r);
            return;
        }

        // それ以外
        add(a, b, x, 2*k+1, l, (l+r)/2);
        add(a, b, x, 2*k+2, (l+r)/2, r);
        data[k] = data[2*k+1] + data[2*k+2];
    }

    /**
     * 最初に呼ぶ際は、query(a, b, 0, 0, size)として呼ぶ.
     * @param a 求める区間の下限（含む）
     * @param b 求める区間の上限（含まない）
     * @param k 確認するノードのindex
     * @param l 確認するノードの下限（含む）
     * @param r 確認するノードの上限（含まない）
     * @return 区間[a, b)の和
     */
    public long max(int a, int b, int k, int l, int r){
        // 区間外
        if(b <= l || r <= a) return 0;
        eval(k, l, r);
        // 完全に含む
        if(a <= l && r <= b) return data[k];
        // それ以外
        long vl = max(a, b, 2*k+1, l, (l+r)/2);
        long vr = max(a, b, 2*k+2, (l+r)/2, r);
        return Math.max(vl, vr);
    }
}