#include <bits/stdc++.h>
using namespace std;

struct cmp
{
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        return a.second > b.second;
    }
};

bool check(vector<pair<int, int>> &a, int m, int n, int mid)
{

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

    int workerIdx = 0;
    int i = 1;

    while (i < n)
    {
        while (true)
        {
            if (workerIdx == m)
                break;
            if (a[workerIdx].first > i)
            {
                break;
            }
            else if (a[workerIdx].first <= i && a[workerIdx].second > i)
            {
                pq.push(a[workerIdx]);
                workerIdx++;
            }
            else
            {
                workerIdx++;
            }
        }

        while (true)
        {
            if (pq.size() == 0)
                return false;
            auto topRange = pq.top();
            pq.pop();

            if (topRange.second <= i)
            {
                continue;
            }
            i = min(topRange.second, i + mid);
            break;
        }
    }

    return true;
}

int minimumTime(int N, int M, vector<pair<int, int>> &Range)
{
    sort(Range.begin(), Range.end());

    int start = 0;
    int end = N;
    int ans = -1;

    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (check(Range, M, N, mid))
        {
            ans = mid;
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
    return ans;
}

int main()
{
    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> Range(M);
    for (int i = 0; i < M; i++)
    {
        cin >> Range[i].first >> Range[i].second;
    }
    cout<<minimumTime(N,M,Range)<<endl;
}