#include <bits/stdc++.h>
#define ll long long int
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define plli pair<long long int , long long int>
#define pcc pair<char,char>
#define pbb pair<bool,bool>
#define PB push_back
#define PF push_front
#define MOD 1000000007
#define intxt freopen("input.txt","r",stdin)
#define outtxt freopen("output.txt","w",stdout)
using namespace std;
const int MAXN = 3e4 + 10;
const ll inf = 1e17;
ll n ,m ,q1 ,q2 ,h[MAXN];
vector <pair<ll,ll>> adj[MAXN];
set <pair<ll,ll>> p;
inline void dijkstra(ll x) {
for(int i = 0 ; i < n ; i++) {
h[i] = inf;
if(i == x) {
h[i] = 0;
}
p.insert({h[i] , i});
}
for(int i = 0 ; i < n ; i++) {
ll v = (*p.begin()).s;
p.erase(*p.begin());
for(auto [u , w] : adj[v]) {
if(h[u] > h[v] + w) {
p.erase({h[u] , u});
h[u] = h[v] + w;
p.insert({h[u] , u});
}
}
if(!p.size()) {
break;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin >> n >> m;
ll s ,e;
for(int i = 1 ; i <= m ; i++) {
cin >> q1 >> q2;
if(i == 1) {
s = q1;
}
if(i == 2) {
e = q2;
}
for(int i = 1 ; q1 + (i * q2) < n ; i++) {
adj[q1].PB({q1 + (i * q2) , i});
}
for(int i = 1 ; q1 - (i * q2) >= 0 ; i++) {
adj[q1].PB({q1 - (i * q2) , i});
}
}
dijkstra(s);
cout << h[e];
}
//Hello
