PKU 2665. Trees

나무들

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 5383	Accepted: 3713

설명

Peking 대학의 동쪽 문에서 조금 떨어진 곳에 있는 길에는 많은 나무들이 있었습니다. 그러나 지하철이 그 근방으로 다니게 되면서 많은 나무들이 잘리거나 다른 곳에 심어지는 일이 발생하였습니다. 이제 나무가 얼마나 남았는지를 세어주세요.

길의 한쪽 방향만 세어야 합니다. 시작지점으로 1미터 간격으로 나무가 심어져 있다는 것을 알아두세요.  이러한 길의 몇몇 부분은 전철역이나 선로나 다른 건물로 인하여 나무들이 잘리거나 다른 곳에 심게 됩니다.  당신이 해야 할 일은 나무가 얼마나 남아있는지를 알아내는 거지요.

예를 들면, 300미터의 길이라면 길의 시작지점부터 나무가 심어져 있으므로 나무는 301그루가 심어져 있는겁니다. 여기서, 길의 시작지점으로부터 100미터부터 200미터 까지 의 길이에 전철역이 들어선다면, 101그루의 나무가 길에서 사라지므로 200그루의 나무가 남아있게 되는 겁니다.

입력

입력에는 여러 테스트 케이스들이 있습니다. 각 케이스들은 길의 길이를 나타내는 정수 L (1 <= L < 2000000000)과 전철역 공사로 인해 본래의 길에서 사용될 구간이 총 몇 구간인지를 나타내는 정수 M (1 <= M <= 5000)으로 시작합니다.

그 뒤에는 M개의 줄이 나오는데, 각 줄은 공사에 사용될 구간을 구체적으로 나타냅니다. 다음과 같은 형식으로 말이지요:

시작 끝

이 시작과 끝 (0 <= Start <= End <= L)은 둘 다 음이 아닌 정수로, 공사 구간의 시작 지점과 끝 지점을 나타냅니다. 이 공사하는 구간들끼리 겹치면 안되는 것은 당연하겠지요.

L = 0 과 M = 0 을 입력하면 입력을 종료합니다.

출력

각 테스트 케이스에 따라 나무가 몇 그루나 남게 되는지 출력하세요.

입력 예시

300 1
100 200
500 2
100 200
201 300
0 0

출력 예시

200
300

Source

Beijing 2005 Preliminary