// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
/*
link:
*/
#include<iostream>
#include<vector>
#include<set>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair
//constexpr int PRI = 1000696969;
constexpr int INF = 1e9, N = 1e6 + 10, MOD = 1e9 + 7;
int b[N], x[N];
int d[N];
vector<int> vc[N];
int main() {
ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);
int n, m; cin >>n >>m;
for(int i = 0; i < m; i++) {
cin >>b[i] >>x[i];
vc[b[i]].push_back(i);
}
for(int i = 0; i < n; i++) d[i] = INF;
d[b[0]] = 0;
set<pair<int, int> > st;
st.insert({0, b[0]});
while(!st.empty()) {
int p = st.begin() -> second; st.erase(st.begin());
if(p == b[1]) {
return cout<<d[p], 0;
}
for(auto j : vc[p]) {
for(int cnt = 1; p + cnt * x[j] < n; cnt++) {
int pq = p + cnt * x[j];
if(d[p] + cnt < d[pq]) {
st.erase({d[pq], pq});
d[pq] = d[p] + cnt;
st.insert({d[pq], pq});
}
}
for(int cnt = 1; p - cnt * x[j] >= 0; cnt++) {
int pq = p - cnt * x[j];
if(d[p] + cnt < d[pq]) {
st.erase({d[pq], pq});
d[pq] = d[p] + cnt;
st.insert({d[pq], pq});
}
}
}
}
cout<<-1;
return 0;
}
