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 {
	static class pair implements Comparable<pair>{
		long x,h;
		pair(long xx,long hh){x=xx;h=hh;}
		@Override
		public int compareTo(pair o) {
			return Long.compare(x,o.x);
		}
		
	}
	public static void main(String[] args) throws Exception {
		MScanner sc=new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt(),d=sc.nextInt(),a=sc.nextInt();
		pair[]in=new pair[n];
		for(int i=0;i<n;i++) {
			in[i]=new pair(sc.nextLong(), sc.nextLong());
		}
		Arrays.sort(in);
		int i=0;
		PriorityQueue<Long>pq=new PriorityQueue<Long>();
		TreeSet<Long>xs=new TreeSet<Long>();
		HashMap<Long, Long>map=new HashMap<Long, Long>();
		
		long range=in[0].x+2l*d;
		long tot=0;
		long ans=0;
		while(i<n) {
			long damage=0;
			long nxtrange=-1;
			while(i<n && in[i].x<=range) {
				xs.add(in[i].x);
				pq.add(in[i].h+tot);
				map.put(in[i].x, in[i].h+tot);
				i++;
			}
			if(i!=n) {
				nxtrange=in[i].x-2l*d;
			}
			while(!xs.isEmpty() && (nxtrange==-1 || xs.first()<nxtrange)) {
				damage=Math.max(damage, (map.get(xs.first())-tot+a-1)/a);
				xs.pollFirst();
			}
			ans+=damage;
			tot+=damage*a;
			while(!pq.isEmpty() && pq.peek()<=tot) {
				pq.poll();
			}
			range=nxtrange+2l*d;
		}
		pw.println(ans);
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] takearr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] takearrl(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public Integer[] takearrobj(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] takearrlobj(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}