時間制限:1000ミリ秒
メモリ制限:65536KB
問題
北京大学の東口から離れた所にある道は、多くの木で飾られている。しかし、地下鉄の建設のため、多くの木が減らされたり、動かされたりする。多くの木が残される方法を数えるのを手伝って欲しい。今、道の片方だけを考慮することにする。木は道の始まりから1mごとに植えられている。現在、道の上のいくつかの部分については、地下鉄駅や他の建物のために、その部分にある木が切り倒されるか、動かされることになっている。残る木の数を数えるプログラムを作成せよ。
例えば、道の長さが300mであるとする。木は道の始まりから1mごとに植えられているので、道には301本の木があったことになる。今、道の始まりから100m～200mの区間は地下鉄駅になるので、この区間の木は移動される。これにより、200本の木が残ることになる。
入力
入力はいくつかのテストケースを含む。各テストケースの最初の行には、道の長さを示す正の整数L(1 <= L < 2,000,000,000)と、木が移動される区間の数を示す整数M(1 <= M <= 5000)が空白区切りで書かれている。次のM行には、各区間の情報として、2つの整数が空白区切りで書かれている。最初の整数は始点=Start, 次の整数は終点=Endである(0 <= Start <= End <= L)。これらは、その区間が道の始まりからStart(m)～End(m)の範囲にあることを示す。各区間が互いに重なることはない。L = M = 0の場合は、テストケースの終端を示す。
出力
各テストケースに対して、各行に残る木の数を表す1つの整数を出力せよ。
入力の例
300 1 100 200 500 2 100 200 201 300 0 0
出力の例
200 300
出典
Beijing 2005 Preliminary