这最短路的建图怎么和网络流一样玄学……
一个最朴素的想法是从每一个点向它能到达的所有点连边，边权为跳的次数，然后跑最短路（然而边数是$O(n^2)$除非自创复杂度比spfa和dijkstra还有优秀的做法否则根本过不了）
那么考虑一下分块
把每一座建筑拆成$O(\sqrt{n})$层，第$i$层代表在这一层只能每一步跳$i$个建筑，然后这一层每一个建筑向它能到达的点连双向边
然后每一层每一个建筑向底层连边，代表如果这里有其他狗就可以更换跳的步数
然后考虑每一只狗，如果它每一步跳的步数小于$\sqrt{n}$，那么直接把它向对应建筑对应层数的点连边
如果大于$\sqrt{n}$，直接暴力向它能到达的点连边，那么连边的条数不会超过$O(logn)$
所以实际的边数不会超过$O(nlogn)$，那么就跑一个最短路就好了
然而似乎spfa诈尸……这题卡dijkstra只能用spfa
然而数据很诡异块的大小得调成$min(\sqrt{n},100)$
差不多就这样
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define id(i,k) ((n*k)+i)
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=N*;
int ver[M],Next[M],head[M],edge[M],tot;
int vis[M],dis[M];queue<int> q;
int b[N],p[N],n,m,block,ans;
inline void add(int u,int v,int e){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;
}
int spfa(int s,int t){
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
q.push(s),vis[s]=,dis[s]=;
while(!q.empty()){
int u=q.front();q.pop(),vis[u]=;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(cmin(dis[v],dis[u]+edge[i]))
if(!vis[v]) q.push(v),vis[v]=;
}
}
return dis[t];
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();
block=min(,(int)sqrt(n));
for(int i=;i<=block;++i){
for(int j=;j+i<n;++j){
add(id(j,i),id(j+i,i),),
add(id(j+i,i),id(j,i),);
}
for(int j=;j<n;++j) add(id(j,i),j,);
}
for(int i=;i<m;++i){
b[i]=read(),p[i]=read();
if(p[i]<=block) add(b[i],id(b[i],p[i]),);
else{
for(int j=b[i]-p[i];j>=;j-=p[i])
add(b[i],j,(b[i]-j)/p[i]);
for(int j=b[i]+p[i];j<n;j+=p[i])
add(b[i],j,(j-b[i])/p[i]);
}
}
ans=spfa(b[],b[]);
printf("%d\n",ans!=0x3f3f3f3f?ans:-);
return ;
}