//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 6
#define N 500005
using namespace std;
ll n, m;
ll b[N], p[N];
ll d[N];
vector<ll> vt[N];
ll ed, st;
void dij() {
for (int i = 0; i < n; i ++) {
d[i] = inf;
}
d[st] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, st});
while (pq.size()) {
auto u = pq.top().se;
auto c = pq.top().fi;
pq.pop();
if (c > d[u]) continue;
for (auto it : vt[u]) {
for (int j = 1; u + j * it < n; j ++) {
ll v = u + j * it;
if (d[v] > d[u] + j) {
d[v] = d[u] + j;
pq.push({d[v], v});
}
}
for (int j = 1; u - j * it >= 0; j ++) {
ll v = u - j * it;
if (d[v] > d[u] + j) {
d[v] = d[u] + j;
pq.push({d[v], v});
}
}
}
}
}
signed main(void) {
faster;
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
cin >> b[i] >> p[i];
if (i == 2) {
ed = b[i];
}
if (i == 1) {
st = b[i];
}
vt[b[i]].push_back(p[i]);
}
dij();
if (d[ed] == inf) {
cout << -1;
}
else {
cout << d[ed];
}
return 0;
}
