あいずにゃんは若ヶ松高校のプログラミングコンテスト部、通称ぷろこん部に所属する2年生である。天使のようにかわいい。 あいずにゃんは今年の夏フェスに参加する予定なので、聴きに行くバンドのスケジュールを立てた。 ここで心配なのが日焼けだ。 ライブはすべて野外で行われるが、あいずにゃんは日焼けしやすい体質なので長時間野外で紫外線を浴びすぎるとすぐ日焼けしてしまう。 ライブがない間は屋内に避難することでできるだけ紫外線を回避するつもりだが、ライブ中はどうしても日に当たってしまう。 そこであいずにゃんは日焼け止めを塗ることで紫外線対策をすることを考えた。
日焼け止めを塗ると、塗った時間からT分間だけその効果を得ることができる。 日焼け止めは1回しか塗ることができないため、効果的に使いたい。 あいずにゃんは、ライブの開始時刻から終了時刻までは野外にいて、それ以外では屋内にいる。 あいずにゃんが聴く予定のライブスケジュールが与えられるので、野外にいる間で日焼け止めの効果を得られる最大の時間の長さを求めよ。
入力は次の形式で与えらえる。
T N s_1 t_1 ... s_N t_N
1行目では日焼け止めの効果を得られる時間を表す整数Tが与えられる。 2行目ではあいずにゃんが聴くライブの数を表す整数Nが与えられる。 続くN行には、あいずにゃんがi番目に聴くライブの開始時刻を表す整数s_iと終了時刻を表す整数t_iが空白区切りで与えられる。
野外にいる間で日焼け止めの効果を得られる最大の時間の長さを1行で出力せよ。
20 1 0 10
10
20 1 0 100
20
9 3 1 5 9 11 13 20
7
25 5 9 12 15 20 21 25 28 40 45 60
21