시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 144 55 40 40.404%

문제

라이언은 여행을 정말 좋아한다. 하루라도 여행 중이 아니면 입 안에 가시가 돋을 정도였는데, 그렇게 여행만 다니다 보니 체력과 예산이 버텨주지 않아서, 여행 중이 아닌 기간을 가능한 한 짧게 하는 걸로 목표를 바꾸기로 했다.

라이언이 여행 계획을 짜는 방식은 다음과 같다. 먼저 어느 곳을 어떤 기간 동안 갈 수 있는지를 조사한 목록을 만든다. 이 기간은 교통편, 휴일, 특정일에만 있는 행사 등 정말 많은 요소를 고려하여 정한 것이기 때문에 바꿀 수는 없다. 즉, 목록에 있는 여행지에 대해서 정해진 기간 그대로 가거나 가지 않는 두 가지 경우만 선택할 수 있다. 동시에 두 곳을 여행하는 것은 불가능하기 때문에 선택한 여행지 간 기간이 겹치는 경우는 없어야 한다. 물론 여행지 A에서 오전에 돌아온 다음 오후에 여행지 B로 떠나는 일정도 생각해볼 수 있겠지만, 체력을 고려하여 그런 경우는 만들지 않기로 했다.

앞에서 밝혔듯 라이언의 목표는 여행 중이 아닌 기간을 가능한 한 짧게 하는 것이다. 즉, 여행 중이 아닌 기간의 최댓값을 최소로 하는 계획을 짜는 것이다. 예를 들어 7월 1일부터 7월 31일까지의 기간 동안의 여행 계획을 짜는 경우를 생각해보자. 여행지 목록과 각각의 기간은 다음과 같다.

  • 제주도: 7월 20일 ~ 7월 23일
  • 런던: 7월 3일 ~ 7월 14일
  • 도쿄: 7월 5일 ~ 7월 7일
  • 홍콩: 7월 12일 ~ 7월 15일
  • 하와이: 7월 24일 ~ 7월 29일

각 구간 별로 겹치지 않게 여행지를 선택하는 방법의 예시로는 런던 - 제주도 - 하와이, 도쿄 - 홍콩 - 제주도 - 하와이 등이 있다. 이 중 전자의 구간의 경우 여행 중이 아닌 기간은 7월 1일 ~ 2일, 7월 15일 ~ 19일, 7월 30일 ~ 31일로, 이 중 최대 기간은 5일이다. 후자의 경우 여행 중이 아닌 기간은 7월 1일 ~ 4일, 7월 8일 ~ 11일, 7월 16일 ~ 19일, 7월 30일 ~ 31일로, 이 중 최대 기간은 4일이다. 라이언의 기준에 따르면 여행 중이 아닌 기간의 최댓값이 최소가 되어야 하므로 후자의 구간대로 여행지를 선택해야 한다.

여행 계획을 짜려는 구간과 여행 기간의 후보가 주어졌을 때, 여행 중이 아닌 기간의 최댓값(여행 중이 아닌 기간 중 가장 긴 기간 길이)을 최소로 하는 방법을 찾아 그 기간을 출력하시오.

입력

첫 줄에 N(1 ≤ N ≤ 1,000)이 입력되며, 이는 여행 계획을 짜려는 구간의 길이를 의미한다.

둘째 줄에 M(1 ≤ M ≤ 1,000)이 입력되며, 이는 여행 기간의 후보의 수를 의미한다.

다음으로 M개의 줄에 걸쳐 두 정수 ai와 bi (1 ≤ ai ≤ bi ≤ N)가 입력되며, 이는 여행 기간의 시작과 끝을 의미한다. 각각의 값은 시작일로부터 몇 번째 날인지를 의미하며, 구간의 첫 번째 날에 대응되는 값이 1이 된다.

출력

첫 줄에 여행 중이 아닌 기간의 최댓값의 최소를 출력한다.

예제 입력 1

31
5
20 23
3 14
5 7
12 15
24 29

예제 출력 1

4