C. Амралт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландын суруулиуд амарчээ. Сургуулийн амралт $n$ өдөр үргэлжилнэ. Сургуулийн хүүхдүүд амралтаа өнгөрүүлж байх хооронд Мэдээлэл зүйн багш Марина Сергейна бүхэл зуны турш Берландын Улсын Шалгалтын материалыг засч байгаад эцэст нь амралтын завсарлага авчээ. Өдөр бүр зарим ажилчид хуваарийн дагуу ирж цэцэг усална. Гэвч Марина Сергейна өөрийн хуваарт өдрөө ажлаасаа үнэхээр залхсан байх ба магадгүй алдаа хийсэн байж болох амралтынхаа талаар мөрөөдөлд автана. Үнэн хэрэгтээ амралтын үеэр хуваарийн дагуу цэцэг услагдахгүй байж болно эсвэл олон удаа усалж болно.

Оролт

Эхний мөрөнд Берландын амралтын өдрийн тоо, хуваарийн дагуу цэцэг услах ажилчдын тоог харуулсан $n$ болон $m$ ($1 ≤ n, m ≤ 100$) гэсэн тоо агуулна. Дараагийн $m$ мөрүүд нь хуваарьт өдрийн тодорхойлолтыг агуулсан байна. Мөр тус бүр нь $a_{i}$ and $b_{i}$ ($1 ≤ a_{i} ≤ b_{i} ≤ n$) гэсэн хоёр тоо агуулах ба энэ нь $i$ дахь цэцэг услах үүрэгтэй хүн $a_{i}-b_{i}$ дахь өдөрт нэг удаа цэцэг усална. Хуваарийн дагуу хариуцлага өдөр өдрөөр дараалан шилжинэ. Өөрөөр хэлбэл $1$ -ээс $m - 1$ хүртэл бүх $i$ хүнд $b_{i} ≤ a_{i + 1}$ байхаар үргэлжилнэ.

Гаралт

Хуваарьт ямар нэг алдаа мадаг байхгүй бол OK гэж гарга. Үгүй бол цэцгийг хамгийн багадаа услагдах болон услагдахгүй өдрийн тоог ол. Гаралт нь өдрийн тоо болон тухайн өдрөө цэцгийг услах тоог агуулсан хоёр тоо байна.

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
10 5
1 2
3 3
4 6
7 7
8 10
Гаралт
OK
Оролт
10 5
1 2
2 3
4 5
7 8
9 10
Гаралт
2 2
Оролт
10 5
1 2
3 3
5 7
7 7
7 10
Гаралт
4 0

Тэмдэглэл

Хоёр дахь загварт хоёр болон зургaа дахь өдөр цэцэг услаагүй учир алдаа гарсан байна гэж үзнэ. Гэвч та хоёр дахь өдрийг гаргах ёстой ба өөрөө хэлбэл хамгийн бага услагдсан өдөр юм.

Сэтгэгдлүүдийг ачааллаж байна...