A. Шүүгээ

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

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

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

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

Стокхолмын манантай нэгэн өглөө Карлсон түүний найз Лилеброр Свантенсоны байшинд байгаа чанамалаар хөнгөхөн хооллохоор шийдсэн. Карлсоны аз болоход тэдний найзын гэрт хэн ч байсангүй. Карлсон удаан өлсгөлөн байж чадахааргүй байсан учир байшингаас хооллохоор шийдсэн.

Карлсоны хараа шууд гал тогоонд байх $n$ аяганы шүүгээн дээр тусав. Карлсон эдгээр шүүгээнүүдэд чанамалын нөөц нуугдаж байгаа гэдгийг шууд ойлгосон. Карлсон гал тогоог тойрон нисч эхэлсэн ба шүүгээнүүдийн хаалгыг нээж, хааж өөрийн олж чадах чанамалын бүх шилийг хоослосон.

Одоо бүх чанамалын шил хоосон болсон, Карлсон цадчихсан ба өөрийн ул мөрийг үлдээхийг хүссэнгүй мөн найзыгаа гомдоохыг хүссэнгүй. Аяганы шүүгээ бүр хоёр хаалгатай ба зүүн, баруун хаалгатай. Карлсон түүнийг гал тогоонд орж ирэхэд зүүн хаалганууд ижил байрлалтай байсан (нээлттэй эсвэл хаалттай), мөн адил баруун хаалганууд ижил байрлалтай байсан (нээлттэй эсвэл хаалттай) гэдгийг санаж байна. Карлсон гэр бүл ирэхээс өмнө хаалгануудыг уг нөхцөлийг хангаж байхаар буцаахыг хүсч байна. Карлсон зүүн болон баруун хаалгануудын байрлалыг санахгүй байна. Түүнчлэн түүний хувьд бүх зүүн болон баруун хаалганы байрлал ямар байх нь хамаагүй. Харин бүх зүүн хаалга ижил байрлалтай, мөн бүх баруун хаалга ижил байрлалтай байх нь чухал. Жишээлбэл бүх зүүн хаалга хаалттай, мөн бүх баруун хаалга нээлттэй байж болох юм.

Карлсон шүүгээний хаалгыг нээх эсвэл хаахад нэг секунд зарцуулна. Тэр гэр бүл буцаж ирэхэд маш бага хугацаа үлдсэнийг ойлгосон ба бүх хаалгыг шаардлагатай байрлалд нь аваачихад шаардлагатай $t$ хугацааны (секундээр) хамгийн бага тоог мэдэхийг хүсч байна.

Таны ажил бол шаардлагатай $t$ хугацааны тоог секундээр олох юм.

Оролт

Оролтын эхний мөрөнд нэг бүхэл тоо $n$ байх ба гал тогооны шүүгээний тоо байна ($2 ≤ n ≤ 10^{4}$). Тэгээд $n$ мөр байх ба мөр бүрт хоёр бүхэл тоо $l_{i}$ ба $r_{i}$ $(0 ≤ l_{i}, r_{i} ≤ 1)$ байна. Хэрвээ $i$-р шүүгээний зүүн хаалга онгорхой байвал $l_{i}$ нь нэгтэй тэнцүү байх бол хаалттай тохиолдолд тэгтэй тэнцүү байна. Үүнтэй адилаар хэрвээ $i$-р шүүгээний баруун хаалга онгорхой байвал $r_{i}$ нь нэгтэй тэнцүү байх бол хаалттай тохиолдолд тэгтэй тэнцүү байна.

Нэг мөрөнд байгаа тоонууд зайгаар тусгаарлагдана.

Гаралт

Карлсон шүүгээнүүдийн хаалгыг хэрэгтэй байрлалд нь оруулахад шаардлагатай хугацааны хамгийн бага утгыг илэрхийлэх $t$ (секундээр) тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5
0 1
1 0
0 1
1 1
0 1
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...