#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> B(m), P(m);
    for (int i = 0; i < m; i++) {
        cin >> B[i] >> P[i];
        // اگر ورودی 1-based باشه:
        // B[i]--;
    }
    // برای هر موقعیت، سگهایی که اونجا هستن
    vector<vector<int>> dogs_at_pos(n);
    for (int i = 0; i < m; i++) {
        dogs_at_pos[B[i]].push_back(i);
    }
    vector<int> dist(m, INF);
    using pii = pair<int,int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (u == 1) break; // جواب پیدا شد
        int bu = B[u], pu = P[u];
        int rem = bu % pu;
        // همهی موقعیتهایی که دوج u میتونه برسه
        for (int x = rem; x < n; x += pu) {
            int cost = abs(x - bu) / pu;
            // همهی دوجهایی که سر این موقعیت هستن
            for (int v : dogs_at_pos[x]) {
                int nd = d + cost;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.push({nd, v});
                }
            }
        }
    }
    if (dist[1] == INF) cout << -1 << "\n";
    else cout << dist[1] << "\n";
    return 0;
}
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... | 
| # | Verdict | Execution time | Memory | Grader output | 
|---|
| Fetching results... |