#include
using namespace std;
struct edge { int t, v; edge* next; };
const int maxn = 30009; const int bsz = 80; const int maxb = 83; const int maxnd = maxn * maxb; const int ebsz = 1000001;
int n, m, st, te, d[maxnd], tnid, nid[maxb][maxn]; edge *head[maxnd];
inline void addEdge(int u, int v, int w) { static edge* ebuf; static int cnt(0); if (!cnt –) ebuf = new edge[ebsz], cnt = ebsz - 2; ebuf-> t = v; ebuf-> v = w; ebuf-> next = head[u]; head[u] = ebuf ++; }
#define recycle(x) {
if (x == maxn)
x = 1;
}
void SPFA() { static int q[maxnd]; static bool inq[maxnd]; int hd(0), tl(1); memset(inq, 0, sizeof(inq)); memset(d, -1, sizeof(d)); d[q[0] = st] = 0; while (hd != tl) { int p(q[hd ++]); recycle(hd); inq[p] = 0; for (edge* e = head[p]; e; e = e-> next) if (d[e-> t] == -1 || d[e-> t] > d[p] + e-> v) { d[e-> t] = d[p] + e-> v; if (!inq[e-> t]) { inq[e-> t] = 1; q[tl ++] = e-> t; recycle(tl); } } } }
int main() { memset(head, 0, sizeof(head)); scanf("%d%d", &n, &m); tnid = n; for (int i = 1; i <= bsz; ++ i) { for (int j = 0; j < n; ++ j) { nid[i][j] = tnid ++; addEdge(nid[i][j], j, 0); } for (int j = 0; j + i < n; ++ j) { addEdge(nid[i][j], nid[i][j + i], 1); addEdge(nid[i][j + i], nid[i][j], 1); } } for (int i = 0; i < m; ++ i) { int b, p; scanf("%d%d", &b, &p); if (i == 0) st = b; else if (i == 1) te = b; if (p > bsz) { for (int j = b % p; j < n; j += p) addEdge(b, j, abs(b - j) / p); } else addEdge(b, nid[p][b], 0); } SPFA(); printf("%d\n", d[te]); }