농부 창호는 요즈음 대유행중인 무서운 소로나 바이러스(COWVID-19) 때문에
고민이 많다.

농부 창호는 소들의 오후 일과를 위해, 일직선 좌표계로 표현되는 목장에
각 N마리의 소들을 배치시키려고 한다. 

목장 내에는 [s,e]로 표현되는 M개의 구간이 있으며, 이 구간 내에 있는 풀은 잘 자라서 먹을 수 있다. 

농부 창호는
모든 소들을 이 구간 내에 배치시키되, 사회적 거리두기를 위해 소들간의 거리를 최대화시키고자 한다. 

구체적으로는, 두 소 사이의 거리의 최솟값이 D라고 하면, D를 최대화시키려고 한다. 

이 D를 구하는 프로그램을 작성하라. (소들은 무조건 정수 좌표 위에 배치되며, 구간 [s,e]에서 각 경계 좌표인 s와
e에도 소들이 위치할 수 있다.) 

첫 줄에 정수 N과 M이 주어진다. (2≤N≤​100,000, 1≤​M≤​100,000)

다음 M줄에 걸쳐서, 소들이 먹을 수 있는 풀이 있는 구간인 s e가 공백을 사이에 두고 주어진다.

각 좌표는 1이상 10^​18이하의 정수이다.

그 어떤 두 구간도 겹치거나 맞닿지 않는다.

D의 최댓값을 첫 줄에 출력한다. D>0인 답이 나올 수 있는 입력예시가 항상 보장된다.

​

D=2를 만족시키는 한 가지 방법은 소들을 각각 x = 0, 2, 4, 6, 9에 배치하는 것이다.