A. Инна ба сэрүүлэгтэй цаг

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

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

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

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

Инна их унтах дуртай, тэгэхээр түүнийг босоход нийт $n$ сэрүүлэгтэй цаг хэрэгтэй. Иннагийн өрөөг зүүн доод буландаа $(0, 0)$ цэгтэй, баруун дээд буландаа $(100, 100)$ цэгтэй $100 × 100$ хэмжээтэй талбай байна гэж бодъё. Дараа нь сэрүүлэгтэй цагнууд энэ талбайн бүхэл тоон координатуудад байрлана.

Өглөө боллоо. Иннагийн өрөөнд бүх $n$ сэрүүлэгтэй цагнууд дуугарч байгаа учраас Инна тэдгээрийг унтраахыг хүснэ. Үүний тулд Иннад хөгжилтэй тоглоом гарч ирж байна:

  • Эхлээд Инна тоглоомын туршид ашиглах хэсгийн төрлийг сонгоно. Хэсгүүд нь хэвтээ эсвэл босоо төрлийн аль нэг байна.
  • Дараа нь Инна хэд хэдэн шилжилт хийнэ. Нэг шилжилтэнд Инна тоглоомын эхэнд түүний сонгосон төрлөөр (хэвтээ эсвэл босоо) талбайн ямар нэг урттай хэсгийг будаад дараа нь тухайн хэсгийн бүх сэрүүлгийг унтраана. Бүх сэрүүлгүүд унтарсан тохиолдолд тоглоом дуусна.

Инна үнэхээр нойрмог, тэгэхээр тэр аль болох хурдан сэрүүлэгтэй цагнуудыг шууд авах хүсэлтэй байгаа. Тэр бүх сэрүүлэгтэй цагнуудыг унтраах хэрэгтэй ба үүний тулд тоглоомонд хийх хамгийн бага шилжилтийн тоог олж, түүнд тусал!

Оролт

Оролтын эхний мөр нь сэрүүлэгтэй цагнуудын тоо болох $n$ $(1 ≤ n ≤ 10^{5})$ бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь цагнуудыг тодорхойлно: $i$-р мөр нь $x_{i}$, $y_{i}$ хоёр бүхэл тоог агуулна. Энэ бол $i$-р сэрүүлэгтэй цагны координат $(0 ≤ x_{i}, y_{i} ≤ 100)$.

Өрөөний нэг цэг нь сэрүүлэгтэй цагны ямар нэг тоог агуулж чадах ба сэрүүлэгтэй цагнууд нь өрөөг илэрхийлсэн талбайн талууд дээр байрлана гэдгийг анхаараарай.

Гаралт

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

Орчуулсан: Даариймаа

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

Оролт
4
0 0
0 1
0 2
1 0
Гаралт
2
Оролт
4
0 0
0 1
1 0
1 1
Гаралт
2
Оролт
4
1 1
1 2
2 3
3 3
Гаралт
3

Тэмдэглэл

Эхний жишээнд Инна "Босоо хэсэг"-н төрлийг сонгоод $(0, 0)$, $(0, 2)$ хэсгүүд дээр дуусна, жишээлбэл (1, 0) (1, 1). Тэр хэвтээ хэсгүүдийг зурсан бол дор хаяж 3 хэсгүүд хэрэгтэй болно.

Гурав дахь жишээнд Инна тоглолтын туршид хэсгийн төрлийг өөрчлөх эрхгүй гэдгийг анхаарах нь чухал. Учир нь тоглолтын төгсгөл хүртэл хэвтээ 3, эсвэл босоо 3 хэсгүүд хэрэгтэй.

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