버스 노선

원형 버스 노선에 N개의 정류장이 번호 순서대로 배치되어 있다(1번 → 2번 → ... → N번 → 1번 순환). Q개의 승객이 특정 정류장에서 탑승하고 특정 정류장에서 하차한다. 버스에 동시에 탑승하는 승객 수의 최댓값을 구하고, 그 값 이상을 수용할 수 있는 최소 버스 용량을 구하시오.

입력

첫째 줄에 정류장 수 N과 승객 수 Q가 주어진다. 다음 Q줄에 각 승객의 탑승 정류장 S와 하차 정류장 E가 주어진다. (S ≠ E, 버스는 S에서 탑승하여 순방향으로 이동해 E에 하차)

• 2 ≤ N ≤ 1,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ S, E ≤ N

출력

필요한 최소 버스 용량을 출력한다.

예제 입력

5 3
1 3
2 4
3 5

예제 출력

2