#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MM = 30030, INF = 0x3f3f3f3f;
set<int> adj[MM];
int dis[MM];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> cur;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for(int i=0; i < MM; i++)dis[i] = INF;
int num, paths, a, b; cin >> num >> paths;
int start = -1, dest = -1;
for(int i=0; i < paths; i++){
cin >> a >> b;
if(i == 0){
start = a;
}else if(i==1){
dest = a;
}
adj[a].insert(b);
}
cur.push({0, start});
dis[start] = 0;
while(!cur.empty()){
pii e = cur.top(); cur.pop();
int cit = e.second, price= e.first;
if(cit == dest){
cout << dis[cit]<<'\n';
return 0;
}
if(dis[cit] < price)continue;
for(int u: adj[cit]){
//go up
for(int i=1; cit + i*u < num; i++){
int nn = cit+i*u;
int add= price+i;
if(dis[nn] > add){
dis[nn] = add;
cur.push({add, nn});
}
if(adj[nn].count(u))break;
}
//go down
for(int i=1; cit-i*u >= 0; i++){
int nn = cit-i*u;
int add = price+i;
if(dis[nn]>add){
dis[nn] = add; cur.push({add, nn});
}
if(adj[nn].count(u))break;
}
}
}
cout << -1;
return 0;
}
