// Arup Guha
// Started a long time ago. Finished on 2/10/2015
// Solution to 2009 MCPC Problem A: Up and Down

import java.util.*;

public class a {

	final public static int INF = 1000000000;
	public static TreeMap<Integer,Integer> startSpots;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();

		// Go through each case.
		while (n != 0) {

			int step = stdin.nextInt();
			int num = stdin.nextInt();

			// Read in ladders.
			startSpots = new TreeMap<Integer,Integer>();
			ladder[] jumps = new ladder[num];
			for (int i=0; i<num; i++) {
				int start = stdin.nextInt();
				int end = stdin.nextInt();
				jumps[i] = new ladder(start,end);
				startSpots.put(start, i);
			}

			// num1 = start, num1+1 = end. Make adjacency matrix.
			int size = num+2;
			int[][] adj = new int[size][size];
			fillIn(adj, n, step, jumps);

			// Floyd's is good enough.
			for (int k=0; k<size; k++)
				for (int i=0; i<size; i++)
					for (int j=0; j<size; j++)
						adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);

			// Print result.
			System.out.println(adj[size-2][size-1]);

			// Go to next case.
			n = stdin.nextInt();
		}
	}

	// Fill in the adjacency matrix based on the jumps.
	public static void fillIn(int[][] adj, int n, int s, ladder[] jumps) {

		// Init values.
		for (int i=0; i<adj.length; i++) {
			Arrays.fill(adj[i], INF);
			adj[i][i] = 0;
		}

		// Just for readability.
		int source = adj.length-2;
		int target = adj.length-1;

		// Fill in distances (in jumps) from source and to target.
		for (int i=0; i<jumps.length; i++) {
			adj[source][i] = calc(0, jumps[i].start, s, jumps);
			adj[i][target] = calc(jumps[i].end, n, s, jumps);
		}
		adj[source][target] = calc(0, n, s, jumps);

		// Fill in distances between ending pts of ladders to starting points of ladders
		for (int i=0; i<jumps.length; i++) {
			for (int j=0; j<jumps.length; j++) {
				if (i == j) continue;
				if (jumps[i].end > jumps[j].start) continue;
				adj[i][j] = calc(jumps[i].end, jumps[j].start, s, jumps);
			}
		}
	}

	// Calculates the minimum jumps from start to end for step and jumps.
	public static int calc(int start, int end, int step, ladder[] jumps) {

		// Find next relevant starting point.
		Integer sIndex = null;
		if (startSpots.containsKey(start)) 				sIndex = startSpots.get(start);
		else if (startSpots.higherKey(start) != null)	sIndex = startSpots.get(startSpots.higherKey(start));

		// Starting point of a ladder is not an impediment to optimal jumping.
		if (sIndex == null || end < jumps[sIndex].start + step)
			return (end-start+step-1)/step;

		// Try jumping to each possible spot right after this start spot.
		int bestSpot = -1;
		int bestJumps = INF;
		for (int tryVal = jumps[sIndex].start+1; tryVal<jumps[sIndex].start+step; tryVal++) {
			if (startSpots.containsKey(tryVal)) continue;
			int distance = (tryVal-start+step-1)/step;

			// We update on ties here so we get the farthest along on the same number of jumps.
			if (distance <= bestJumps) {
				bestJumps = distance;
				bestSpot = tryVal;
			}
		}

		// No possible jump in this case.
		if (bestJumps == INF) return INF;

		// Build off the spot bestSpot after bestJumps number of jumps.
		return bestJumps + calc(bestSpot,end,step,jumps);
	}
}

class ladder {

	public int start;
	public int end;

	public ladder(int s, int e) {
		start = s;
		end = e;
	}
}