/*
Code by @marlov
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pi;
#define maxV 30005
long long N,M;
pair<long long,long long> doge[maxV];
map< long long,map<long long,bool> > visited;
//bool visited[maxV][maxV];
queue<long long> cnts[maxV];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(long long i=0;i<M;i++){
cin>>doge[i].first>>doge[i].second;
cnts[doge[i].first].push(i);
}
//bfs
queue< pair< long long,pair<long long,long long> > > q;
q.push(make_pair(0,make_pair(0,doge[0].first)));
visited[0][doge[0].first]=true;
while(!q.empty()){
long long cd=q.front().first;
long long ci=q.front().second.first;
long long cl=q.front().second.second;
q.pop();
//solution
if(ci==1){
cout<<cd<<'\n';
return 0;
}
while(!cnts[cl].empty()){
q.push(make_pair(cd,make_pair(cnts[cl].front(),cl)));
cnts[cl].pop();
}
if(cl-doge[ci].second>=0&&visited[ci][cl-doge[ci].second]==false){
q.push(make_pair(cd+1,make_pair(ci,cl-doge[ci].second)));
visited[ci][cl-doge[ci].second]=true;
}
if(cl+doge[ci].second<N&&visited[ci][cl+doge[ci].second]==false){
q.push(make_pair(cd+1,make_pair(ci,cl+doge[ci].second)));
visited[ci][cl+doge[ci].second]=true;
}
}
cout<<"-1"<<'\n';
return 0;
}
/* stuff you should look for
* long long overflow, array bounds
* special cases (n=1,n=0?)
* do smth instead of nothing and stay organized
*/
