E. МУХ ба маш олон хэрчмүүд

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

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

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

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

Петрбург хотын амьтны хүрээлэнгийн цагаан баавгай болох Мэншиков болон Услада, мөн Киевийн амьтны хүрээлэнгийн Хорэйс заан нар зураг зурахаар болжээ. Тэд анхны урлагийн бүтээлээ цаасан дээр ноороглож гэнэ. Ноорог дээр $n$ ширхэг хэрчмүүд байгаа. Хэрчим бүр босоо эсвэл хэвтээ байрлалтай. Одоо тэд эдгээр хэрчмүүдийн заримыг нь арилган эсвэл заримых нь хэсгийг арилган дараахь нөхцлүүдийг хангах бүтээл бүтээхийг хүсжээ:

  1. Хорэйс бийрээ салгалгүйгээр зургийг зурж чаддаг байхыг хүсжээ. Бийрийг зурсан газар дээгүүр дахин гүйлгэж болно. Тиймээс зураг нэг холбоост байх ёстой юм.
  2. Мэншиков зургийг энгийн байлгахыг хүсжээ. Тэрээр ямар ч цикл агуулаагүй дүрс зурахыг хүсжээ.
  3. Эхлээд бүх хэрчмүүдийн эхлэл ба төгсгөл бүхэл тоон координат дээр байна. Услада бутархай тоонд дүргүй тул зургийг бүх хэрчмүүдийн эхлэл ба төгсгөл нь бүхэл тоон координат дээр байлгахыг хүсжээ.

Ноорог дээрх зарим хэсгүүд үзэсгэлэнтэй хэвээрээ байгаа тул тэд зургаа янзлахдаа үлдсэн хэрчмүүдийн уртуудын нийлбэр хамгийн их байлгахыг эрмэлзэнэ. Чиний даалгавар бол энэхүү боломжит хамгийн их уртыг олох юм.

Оролт

Эхний мөрөнд хэрчмүүдийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 2 \cdot 10^{5}$) гэсэн бүхэл тоо байна. Дараагийн $n$ мөр бүрт хэрчмийн эхлэл болон төгсгөлийн координатуудыг илэрхийлэх дөрвөн бүхэл тоо байна: $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ $(-10^{9} ≤ x_{1} ≤ x_{2} ≤ 10^{9}; -10^{9} ≤ y_{1} ≤ y_{2} ≤ 10^{9})$. Хэрчим бүр давтагдашгүй бөгөөд босоо эсвэл хэвтээ байна.

Хэвтээ хэрчмүүд хоорондоо огтлолцохгүй, босоо хэрчмүүд мөн хоорондоо огтлолцохгүй байхаар өгөгдөнө.

Гаралт

Үлдэх хэрчмүүдийн уртын нийлбэрийн боломжит хамгийн их утгыг хэвлэнэ үү.

Орчуулсан: Бат-Од

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

Оролт
2
0 0 0 1
1 0 1 1
Гаралт
1
Оролт
4
0 0 1 0
0 0 0 1
1 -1 1 2
0 1 1 1
Гаралт
5

Тэмдэглэл

Хоёр жишээнд үүсч болох дүрсүүд:

Эхний жишээнд хоёр хэрчим холбогдоогүй байгаа тул аль нэгийг нь арилгана.

Хоёр дахь жишээнд өгөгдсөн хэрчмүүд цикл үүсгэж байна. Циклгүй болгох дөрвөн боломж бий: нэг, хоёр, эсвэл гуравдугаар хэрчмийг устгах, эсвэл гуравдугаар хэрчмийн голын хэсгийг арилгах. Сүүлийн хувилбарыг зурагт дүрслэв.

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