#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define ll long long
#define mk(a,b) make_pair(a,b)
void solve() {
int n,m;
cin >> n >> m;
vector<pair<int,int>> a(m);
map<int,vector<int>> mp;
for (int i = 0; i < m; i++) {
cin >> a[i].first >> a[i].second;
mp[a[i].first%a[i].second].push_back(i);
}
vector<vector<pair<int,int>>> GRAPH(m,vector<pair<int,int>>());
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (abs(a[j].first-a[i].first)%a[i].second == 0) {
GRAPH[i].push_back(mk(j,abs(a[j].first-a[i].first)/a[i].second));
}
}
}
vector<ll> distance(m,1e18);
distance[0]=0;
set<pair<ll,ll>> s;
for(int i=0;i<m;i++)s.insert(mk(distance[i],i));
while(s.size()){
pair<ll,ll> t=*s.begin();
s.erase(s.begin());
ll ind=t.second;
for(auto i:GRAPH[ind]){
ll nd=distance[ind]+i.second;
if(nd<distance[i.first]){
s.erase(mk(distance[i.first],i.first));
distance[i.first]=nd;
s.insert(mk(distance[i.first],i.first));
}
}
}
if (distance[1] == 1e18) cout << "-1\n";
else cout << distance[1] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
