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.Scanner;
import java.util.TreeMap;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.next());
        int D = Integer.parseInt(scanner.next());
        int A = Integer.parseInt(scanner.next());
        TreeMap<Integer, Integer> m = new TreeMap<>();
        for (int i = 0; i < N; i++) {
            Integer x = Integer.parseInt(scanner.next());
            Integer h = Integer.parseInt(scanner.next());
            m.put(x, h);
        }

        // TreeMap<Integer, Integer> bomb = new TreeMap<>();
        DynamicSegTree bomb = new DynamicSegTree(2_000_000_000);

        long ans = 0;
        while (!m.isEmpty()) {
            Integer at = m.firstKey();
            Integer v = m.firstEntry().getValue();
            int prev = (int) bomb.query(at - D, at + D);
            v -= A * prev;
            if (v <= 0) {
                m.remove(at);
                continue;
            }
            Integer cnt = v / A + (v % A == 0 ? 0 : 1);
            ans += cnt;
            bomb.update(at + D, cnt);
            m.remove(at);
        }

        System.out.println(ans);
    }
}


class DynamicSegTree {
    class Node {
        Node left;
        Node right;
        long val;
    }

    Node root;
    long size;

    public DynamicSegTree(long size) {
        this.size = Long.highestOneBit(size);
        if (size > this.size) {
            this.size <<= 1;
        }
        root = new Node();
    }

    void update(int index, long x) {
        Node curr = root;
        long l = 0, r = size;
        curr.val += x;
        while (r - l > 1) {
            long mid = (l + r) >>> 1;
            if (index < mid) {
                if (curr.left == null)
                    curr.left = new Node();
                curr = curr.left;
                r = mid;
            } else {
                if (curr.right == null)
                    curr.right = new Node();
                curr = curr.right;
                l = mid;
            }
            curr.val += x;
        }
    }

    long query(int a, int b) {
        return query(a, b, root, 0, size);
    }

    private long query(int a, int b, Node curr, long l, long r) {
        if (a <= l && r <= b) {
            return curr.val;
        }
        if (r <= a || b <= l) {
            return 0;
        }

        long left = curr.left == null ? 0 : query(a, b, curr.left, l, (l + r) >>> 1);
        long right = curr.right == null ? 0 : query(a, b, curr.right, (l + r) >>> 1, r);
        return left + right;
    }
}