RT.

#include <bits/stdc++.h>
int n,m,num,hhh,head[3100005],start,end,dis[3100005];
struct edge
{
	int nxt,to,qz,from;
} g[18000005];
void add_edge(int u,int v,int quzhi)
{
	//printf("edge -> %d %d %d\n",u,v,quzhi);
	g[++hhh].nxt=head[u];
	head[u]=hhh;
	g[hhh].to=v;
	g[hhh].qz=quzhi;	
	g[hhh].from=u;
}
int getid(int x,int y)
{
	return x*n+y;
}
std::bitset<3100005> vis;
std::queue<int> q;
void spfa(int a)
{
	memset(dis,0x3f,sizeof(dis));
	dis[a]=0;
	q.push(a);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=g[i].nxt)
		{
			int v=g[i].to;
			if(dis[v]>dis[u]+g[i].qz)
			{
				dis[v]=dis[u]+g[i].qz;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
}
signed main()
{
	scanf("%d%d",&n,&m);
	num=sqrt(n/3);
	for(int i=1;i<=num;i++)
	{
		for(int j=0;j<n;j++)
		{
			int x=getid(i,j);
			add_edge(x,j,0);
			if(i+j<n)
			{
				int y=getid(i,i+j);
				add_edge(x,y,1);
				add_edge(y,x,1);
			}
			else
			{
				break;
			}
		}
	}
	for(int j=0;j<m;j++)
	{
		int b,p;
		scanf("%d%d",&b,&p);
		if(j==0)
		{
			start=b;
		}
		if(j==1)
		{
			end=b;
		}
		if(p<=num)
		{
			add_edge(b,getid(p,b),0);
		}
		else
		{
			for(int i=1;b+i*p<n;i++)
			{
				add_edge(b,b+i*p,i);
			}
			for(int i=1;b-i*p>=0;i++)
			{
				add_edge(b,b-i*p,i);
			}
		}
	}
	if(start==end)
	{
		printf("0");
		return 0;
	}
	for(int i=1;i<=num;i++)
	{
		for(int j=0;j<n;j++)
		{
			int x=getid(i,j);
			if(head[x])
			{
				add_edge(x,j,0);
			}
		}
	}
	spfa(start);
	if(dis[end]>=0x3f3f3f3f)
	{
		printf("-1");
	}
	else
	{
		printf("%d",dis[end]);
	}
	return 0;
}