#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
void solve(){
int n, m;
cin >> n >> m;
vector<pair<int,int>>monsters(m);
vector<set<int>>pos(n);
for (int i = 0; i < m; i++){
int b, p;
cin >> b >> p;
pos[b].insert(p);
monsters[i] = {b,p};
}
vector<long long>dp(n, (long long)1e18);
dp[monsters[0].first] = 0;
priority_queue<pair<long long,int>>pq;
pq.push({0,monsters[0].first});
while(!pq.empty()){
long long dst = -pq.top().first;
int b = pq.top().second;
pq.pop();
//node + pow * x = mn
if (dp[b] != dst)continue;
if (dp[monsters[1].first] == dst){
cout << dst << endl;
return ;
}
if (pos[b].empty())continue;
int pmin = *pos[b].begin();
for (int i = 1; i <= n / pmin; i++){
for (auto p : pos[b]){
bool ok = 0;
int right = b + i * p;
int left = b - i * p;
if (left >= 0){
ok = 1;
if (dp[left] > dst + i){
dp[left] = dst + i;
pq.push({-dst-i,left});
}
}
if (right <= n - 1){
ok = 1;
if (dp[right] > dst + i){
dp[right] = dst + i;
pq.push({-dst-i,right});
}
}
if (!ok)break;
}
}
}
cout << - 1 << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
