#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 2000000000
#define FF first
#define SS second
int n, m;
vector<pair<LL, LL>> intervals;
bool ok(LL d) {
	LL prev = -1LL * INF * INF;
	int cnt = 0;
	for (auto& i : intervals) {
		while (max(prev + d, i.FF) <= i.SS) {
			prev = max(prev + d, i.FF);
			cnt++;
			if (cnt >= n) break;
		}
		if (cnt >= n) break;
	}
	return (cnt >= n);
}
int main() {
	cin >> n >> m;
	intervals.resize(m);
	for (int i = 0; i < m; ++i)
		cin >> intervals[i].FF >> intervals[i].SS;
		sort(intervals.begin(), intervals.end());
		LL lo = 0;//	
		LL hi = 1LL * INF * INF;
		LL res = -1;
		while (lo <= hi) {
			LL mid = (lo + hi) / 2;
			if (ok(mid)) {
				res = mid;
				lo = mid + 1;
			}
			else {
				hi = mid - 1;			
			}
		}
		cout << res << "\n";
	return 0
}