#include <bits/stdc++.h>
#define ll long long
const int maxn = 100100;
const int mod = 1000000007;
class Solution {
public:
    /**
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    ll s[maxn], s2[maxn];
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        int n = a.size();
        int q = query.size()/2;
        s[0]=s2[0]=0;
        for (int i=1;i<=n;i++) {
            s[i]=s[i-1]+a[i-1];
            s2[i]=s2[i-1]+a[i-1]*(ll)a[i-1];
        }
        vector <int> ret;
        for (int i=1;i<=q;i++) {
            int l=query[2*i-2], r=query[2*i-1];
            ll ans = ((s[r]-s[l-1])*(s[r]-s[l-1])-(s2[r]-s2[l-1]))/2;
            ret.push_back(ans % mod);
        }
        return ret;
    }
};

/**
 * struct Interval {
 *    int start;
 *    int end;
 * };
 */
#define LL long long
#define INF 2000000000
#define X start
#define Y end
 
int nn, mm;
vector<Interval> a;
 
bool ok(int d)
{
    LL prev = -1LL * INF * INF;
 
    int cnt = 0;
    for(int kk = 0; kk < a.size(); kk ++)
    {
        Interval i = a[kk];
        while (max(prev + d, (LL)i.X) <= i.Y)
        {
            prev = max(prev + d, (LL)i.X);
            cnt++;
            if (cnt >= nn) break;
        }
        if (cnt >= nn) break;
    }
 
    return (cnt >= nn);
}
bool cmp(Interval x, Interval y)
{
    if(x.X == y.X) return x.Y < y.Y;
    return x.X < y.X;
}
 
 
class Solution {
public:
    /**
     *
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        sort(intervals.begin(), intervals.end(), cmp);
        a.resize(m);
        nn = n;
         for(int kk = 0; kk < intervals.size(); kk ++) a[kk] = intervals[kk];
        int lo = 1;
        int hi = INF;
        int res = -1;
 
        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if (ok(mid))
            {
                res = mid;
                lo = mid + 1;
            }
            else
            {
                hi = mid - 1;
            }
        }
        return res;
    }
};