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 {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int D = sc.nextInt();
        int A = sc.nextInt();

        int[] X = new int[N];
        int[] H = new int[N];
        for (int i=0; i<N; i++) {
            X[i] = sc.nextInt();
            H[i] = sc.nextInt();
        }

        System.out.println(solve(N, D, A, X, H));
    }

    private static long solve(int N, int D, int A, int[] X, int[] H) {
        long count = 0;
        long current = 0;
        List<Pair> bomb = new LinkedList<>();

        List<Pair> monster = new ArrayList();
        for (int i=0; i<N; i++) {
            monster.add(new Pair(X[i], H[i]));
        }
        Collections.sort(monster, new PairComparator().reversed());

        for (int i=0; i<N; i++) {
            Pair m = monster.get(i);
            // System.err.println("m = (" + m.x + ", " + m.h + ")");

            while (bomb.size() > 0) {
                Pair b = bomb.get(0);
                if (b.x < m.x - D) {
                    current -= b.h;
                    bomb.remove(0);
                    // System.err.println("end of bomb range at " + (b.x) + " < " + m.x);
                } else {
                    // System.err.println(b.x + " >= " + (m.x-D));
                    break;
                }
            }

            if (m.h > current*A) {
                long n =  (m.h - current*A) / A;
                if ((m.h-current*A)%A != 0) {
                    n++;
                }
                bomb.add(new Pair(m.x + D, n));
                current += n;
                count += n;

                // System.err.println("add " + n + " bomb at " + (m.x + D));
            }
        }

        return count;
    }


    static class Pair {
        int x;
        long h;

        public Pair(int x, long h) {
            this.x = x;
            this.h = h;
        }
    }

    static class PairComparator implements Comparator {
        public int compare(Object a0, Object b0) {
            Pair a = (Pair)a0;
            Pair b = (Pair)b0;

            return b.x - a.x;
        }
    }

}