22936번 - 주간 달력

주간 달력(주력)은 일요일부터 토요일까지 총 7일간의 일정이 들어있는 달력이다. 

작년 수현이는 일 년 짜리 달력에 코팅 용지를 붙여 사용했는데, 올해는 조금 더 똑똑해져서 주력에 테이프를 이용하여 일정을 나타내려고 한다. 아뿔싸, 주력의 개수가 N개밖에 없는데 일정은 M개나 있다. 눈물을 머금고 주력을 최대한 알차게 사용하고자 한다. 

주력 하나에 들어갈 수 있는 일정의 개수는 제한이 없고, N개의 주력은 서로 연속되어야 한다. 주력의 맨 처음 날짜는 1이상이어야 하고, 요일은 신경 쓰지 않는다. 일정은 테이프를 이용하여 나타내는데, 하나의 일정을 나타내기 위해 불필요하게 테이프를 자르는 경우는 없다고 하자. 예를 들면 하나의 일정을 하나의 주력에 표시할 때 여러 조각으로 나누어 붙이지 않는다는 것이다. 

테이프가 주력의 면적을 가장 많이 차지할 때 , 테이프를 자르는 횟수를 구해보자. 만약 테이프가 주력의 면적을 가장 많이 차지하는 경우가 2개 이상이라면, 해당하는 경우 중에 주력의 시작 날짜가 가장 작을 때의 테이프를 자르는 횟수를 구하자. 

아래의 그림을 보자. 

하늘색과 회색 일정처럼 일정의 일부라도 주력에 포함된다면 일정 개수에 포함된다. 하지만 넓이는 주력 내에 있는 영역만 계산한다.

초록색 일정의 경우 두 개의 주력에 포함된다. 따라서 초록색의 경우 테이프를 2번 잘라야 한다.

위 예시에서 테이프를 자르는 총 횟수는 10번이다. 이유는 아래의 그림과 같다. 

첫째 줄에는 주력의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 일정의 개수 M이 주어진다. (1 ≤ M ≤ 1,000)

이후 M개의 줄에는 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 50,000)

테이프를 자르는 총 횟수를 출력한다.

요일은 상관없다.