#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
inline void solve(){
int n, m;
cin>>n>>m;
vector<pair<int,int>> g[n+1];
for(int i=0; i<m; i++){
int b, p;
cin>>b>>p;
for(int j=b-p, c = 1; j>=0; j -= p, c++) g[b].push_back({j, c});
for(int j=b+p, c = 1; j<n; j += p, c++) g[b].push_back({j, c});
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> vis(n, 0);
vector<int> dist(n, 1e18);
pq.push({0, 0});
dist[0] = 0;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto [ch, w] : g[v]){
if(d + w < dist[ch]){
dist[ch] = d + w;
pq.push({dist[ch], ch});
}
}
}
cout<<(dist[1] == 1e18 ? -1 : dist[1])<<nl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
