#include <bits/stdc++.h> using namespace std; const int MAX = (2e3)+1, INF = 1e9; int n, m, b[MAX], p[MAX], g[MAX][MAX], d[MAX][MAX]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if(i != j) g[i][j] = d[i][j] = INF; for(int i = 0; i < m; i++) cin >> b[i] >> p[i]; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) if(i != j) { if(abs(b[i] - b[j]) % p[i] == 0) g[i][j] = abs(b[i] - b[j]) / p[i]; } queue<int> q; q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); for(int v = 0; v < m; v++) if(u != v && d[0][v] == INF) { d[0][v] = d[0][u] + g[u][v]; q.push(v); } } cout << d[0][1]; }