#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for(int i = 0; i < M; i++){
cin >> B[i] >> P[i];
}
// Birgina binoga nechta doge joylashganini saqlaymiz
vector<vector<int>> doges_at(N);
for(int j = 0; j < M; j++){
doges_at[B[j]].push_back(j);
}
// dist[j] = doge j ga xabar yetib borishi uchun kerak bo'lgan eng kam sakrashlar
vector<ll> dist(M, INF);
dist[0] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
pq.emplace(0, 0);
while(!pq.empty()){
auto [d, i] = pq.top(); pq.pop();
if(d > dist[i]) continue;
if(i == 1) break; // doge 1 ga yetdik
int p = P[i], b0 = B[i];
// Oldinga sakrashlar: b0 + k*p
for(ll k = 1, b = b0 + p; b < N; k++, b += p){
for(int j: doges_at[b]){
ll nd = d + k;
if(nd < dist[j]){
dist[j] = nd;
pq.emplace(nd, j);
}
}
}
// Orqaga sakrashlar: b0 - k*p
for(ll k = 1, b = b0 - p; b >= 0; k++, b -= p){
for(int j: doges_at[b]){
ll nd = d + k;
if(nd < dist[j]){
dist[j] = nd;
pq.emplace(nd, j);
}
}
}
}
ll ans = dist[1];
cout << (ans == INF ? -1 : ans) << "\n";
return 0;
}
