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.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        FastReader scan = new FastReader();
        //PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("marathon.out")));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        Task solver = new Task();
        //int t = scan.nextInt();
        int t = 1;
        for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
        out.close();
    }
    static class Task {
        public void solve(int testNumber, FastReader sc, PrintWriter pw) {
            int n = sc.nextInt();
            int rad = sc.nextInt();
            int dmg = sc.nextInt();
            tup[ ] mo = new tup[n];
            for(int i=0;i<n;i++){
                mo[i]=new tup(sc.nextInt(),sc.nextInt());
            }
            Arrays.sort(mo);
            long curdmg = 0;
            Queue<tup> range = new LinkedList<>();
            long bombs = 0;
            for(tup x : mo){
                while(range.size()>0&&x.a>range.peek().a){
                    curdmg -= range.poll().b;
                }
                long hft = x.b-curdmg;
                long tb = (hft+dmg-1)/dmg;
                if(tb>0) {
                    curdmg += tb * dmg;
                    bombs += tb;
                    range.add(new tup(x.a+2*rad,tb*dmg));
                }
                //pw.println(hft + " " + curdmg+" "+tb);
            }
            pw.println(bombs);
        }
    }
    static class tup implements Comparable<tup>{
        long a, b;
        tup(long a, long b){
            this.a=a;
            this.b=b;
        }

        @Override
        public int compareTo(tup o) {
            return a!=o.a?Long.compare(a,o.a):Long.compare(b,o.b);
        }
    }
    static void shuffle(long[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            long temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}