#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e4 + 5;
int n, m, f[N], a[N];
vector<int> ad[N];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, d; cin >> u >> d;
a[i] = u;
ad[u].push_back(d);
}
for(int u = 0; u < n; u++){
sort(ad[u].begin(), ad[u].end());
ad[u].erase(unique(ad[u].begin(), ad[u].end()), ad[u].end());
reverse(ad[u].begin(), ad[u].end());
}
for(int i = 0; i < n; i++) f[i] = 100'000'000'000'000'000;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({f[a[0]] = 0, a[0]});
while(pq.size()){
auto [d, u] = pq.top(); pq.pop();
if(d != f[u]) continue;
if(u == a[1]) return cout << d, 0;
for(auto w : ad[u]){
for(int i = 1; u + i * w < n; i++){
if(d + i < f[u + i * w]) pq.push({f[u + i * w] = d + i, u + i * w});
}
for(int i = 1; u - i * w >= 0; i++)
if(d + i < f[u - i * w]) pq.push({f[u - i * w] = d + i, u - i * w});
}
}
cout << -1;
return 0;
}
