#include<bits/stdc++.h>
using namespace std;
int w,st,p,c,l[111],x[51],y[51],d[111][111];
set<int>s;
int ds(int b,int d){
	if(b==d)return 0;
	if(s.count(b))return 0x3fffffff;
	int k=d;
	for(int i=1;i<=p;i++){
		if(b<x[i]&&x[i]<k&&(x[i]-b)%st==0)k=x[i];
	}
	if(k!=d&&s.count(k))k--;
	if(k==b)return 0x3fffffff;
	return ds(k,d)+(k-b+st-1)/st;
}
int q(int x){
	return lower_bound(l+1,l+c+1,x)-l-1;
}
void f(){
	for(int k=1;k<=c;k++)for(int i=1;i<=c;i++)for(int j=1;j<=c;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main(){
	cin>>w;
	while(w!=0){
		cin>>st>>p;
		s.clear();
		c=0;
		l[++c]=0,l[++c]=w;
		for(int i=1;i<=p;i++)cin>>x[i]>>y[i],s.insert(x[i]),l[++c]=x[i],l[++c]=y[i];
		sort(l+1,l+c+1);
		c=unique(l+1,l+c+1)-l-1;
		memset(d,0x3f,sizeof(d));
		for(int i=1;i<=p;i++)d[q(x[i])][q(y[i])]=0;
		for(int i=1;i<c;i++){
			for(int j=i+1;j<=c;j++)d[i][j]=min(d[i][j],ds(l[i],l[j]));
		}
		f();
		cout<<d[1][c]<<endl;
		cin>>w;
	}
	return 0;
}
90分，wa在10号点上