#include<bits/stdc++.h>
using namespace std;
//_______________________________________________
const int N=3e4+2;
long long dp1[N];
long long dp2[N];
long long n, m;
vector<pair<int, long long>> a[N];
struct bg
{
int toanha, jump;
};
bg b[N];
//_______________________________________________
void bfs(int dinh, long long dp[])
{
for(int i=0; i<n; i++)dp[i]=INT_MAX;
dp[dinh]=0;
queue<int> qu;
qu.push(dinh);
while(qu.size()!=0)
{
int temp=qu.front(); qu.pop();
for(auto it: a[temp])
{
if(dp[it.first]>dp[temp]+it.second)
{
dp[it.first]=dp[temp]+it.second;
qu.push(it.first);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>b[i].toanha>>b[i].jump;
}
for(int i=1; i<=m; i++)
{
int tam=b[i].jump;
while (b[i].toanha+tam<n)
{
a[b[i].toanha].push_back({b[i].toanha+tam, tam/b[i].jump});
tam+=b[i].jump;
}
tam=b[i].jump;
while (b[i].toanha-tam>=0)
{
a[b[i].toanha].push_back({b[i].toanha-tam, tam/b[i].jump});
tam+=b[i].jump;
}
}
// for(int i=0; i<n; i++)
//
// {
// for(auto it:a[i])cout<<it.first<<" "<<it.second<<" ";
//
// cout<<endl;
// }
bfs(b[1].toanha, dp1);
// bfs(b[2].toanha, dp2);
long long ans=INT_MAX;
// for(int i=0; i<n; i++)ans=min(ans, dp1[i]+dp2[i]);
ans=dp1[b[2].toanha];
if(ans==INT_MAX)cout<<-1;
else cout<<ans;
return 0;
}
