#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9223372036854775807
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)
ll n,m;
vi b,p,vis,_,mindist;
vector<vi> dog;
int main(){
cin >> n >> m; b.assign(m,0); p.assign(m,0);
rep(i,0,m) cin >> b[i] >> p[i];
dog.assign(n,_);
rep(i,0,m) dog[b[i]].push_back(i);
vis.assign(n,0);
priority_queue<ii> pq;
pq.push(make_pair(0,b[0]));
mindist.assign(n,inf);
while (!pq.empty()){
ll dist = -pq.top().first, i = pq.top().second; pq.pop();
if (i == b[1]) {
cout << dist << endl;
exit(0);
}
if (vis[i]) continue;
vis[i] = 1;
rep(j,0,sz(dog[i])){
ll px = p[dog[i][j]],cur = i+px,cnt = 1;
while (cur < n) {
if (!vis[cur] && mindist[cur] > dist+cnt && sz(dog[cur]) > 0) {
pq.push(make_pair(-dist-cnt,cur));
mindist[cur] = dist+cnt;
}
cur += px; cnt++;
}
cur = i-px, cnt = 1;
while (cur >= 0){
if (!vis[cur] && mindist[cur] > dist+cnt && sz(dog[cur]) > 0) {
pq.push(make_pair(-dist-cnt,cur));
mindist[cur] = dist+cnt;
}
cur -= px; cnt++;
}
}
}
cout << -1 << endl;
}
