АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Ойрдоо үүсгэсэн хорлон сүйтгэлдээ харамссан Bessie үнээ уучлалт гуйж Фермер Жонд тусалж тээврээс ирсэн бухлуудыг давхарлаж өрөхөд нь туслахаар болжээ.

Эхлээд түүнд нэг ч бухалгүй N (1 <= N <= 1,000,000, N сондгой) ширхэг 1-ээс N хүртэл дугаарлагдсан байгууламжууд бий. Фермер Жон түүнд К (1 <= K <= 25,000) ширхэг үйлдлийн зааварчилгаа өгнө. Зааварчилгаа болгон "A B" гэсэн хэлбэртэй ба Bessie A-аас B дүгээр байгууламж болгон дээр тус бүр 1 ширхэг бухал давхарлаж өрнө. Жишээ нь: Фермер Жон түүнд "10 13" гэж хэлвэл тэр 10, 11, 12 болон 13-р байгууламжууд дээр тус бүр 1 ширхэг бухал давхарлаж өрнө.

Bessie-г өрж дууссаны дараа байгууламжуудыг өндрөөр нь жагсааж дугаарлаад яг голын байгууламж хэдэн давхар бухалтай гэдгийг мэдэхийг хүссэн.

(N сондгой тул ганц л хариу байгаа).

Input

Эхний мөр: Зайгаар тусгаарлагдсан 2 бүхэл тоо болох N , K.

Хоёроос (1 + K)-р мөр: Мөр болгон Фермер Жоны зааварчилгаа болох зайгаар тусгаарлагдсан бүхэл A , B (1 <= A <= B <= N) тоонууд өгөгдөнө.

Output

Эхний мөр: Бодлогын хариу болох ганц бүхэл тоо.

Example

Input:

7 4

5 5

2 4

4 6

3 5

Output:

1

Орчуулсан : УБ 1-р сургууль Б.Мөнх-Оргил