D. Архитектор Вася

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

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

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

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

Нэгэн удаа Вася тоосгонуудаар тогложээ. Түүнд байсан бүх тоосгонууд нь зөв куб хэлбэртэй байв. Вася авьяаслаг архитектор боловч түүний барьсан барилгууд нь нуран унасаар байжээ.

Уг тоосгонуудаар барилга барих явцыг авч үзье. Вася нэг тоосго аван өмнө нь аль хэдийн барьсан байгаа барилгынхаа орой дээр тавих юм. Түүнчлэн ингэж тоосгоо тавихдаа одоо тавьж буй тоосгоны талууд нь аль хэдийн хэрэглэсэн тоосгонуудын талуудтай параллель байхаар тавих юм. Вася эхний тоосгоо хэвтээ хавтгай дээр байрласан Декартын координатын систем дээр байрлуулжээ. Хавтгай дээрх $i$ дугаартай тоосгоны проекц (тоосгоны суурь) нь талууд нь координатын тэнхлэгүүдтэй параллель байх квадрат бөгөөд уг квадратын эсрэг булангууд нь $(x_{i, 1}, y_{i, 1})$ болон $(x_{i, 2}, y_{i, 2})$ гэсэн цэгүүд дээр байрлалтай байв. Тоосгонуудыг нэгэн жигд хуванцраар хийсэн байх ба $a × a × a$ хэмжээтэй нэг тоосгоны жин нь $a^{3}$ грамм байна.

Мөн Вася өмнө нь тавьсан тоосго дээрээ дахин тоосго тавих болгонд (анхны тоосгонуудыг тавьсан мөчийг тооцохгүй) өмнө тавьсан тоосгоны дээд хэсэг болон дээрээс нь тавьсан тоосгоны доод хэсгийн огтлолцолд үүсэх хэсгийн талбай нь үргэлж эерэг байна.

Бид (Вася мөн хамаарна) физикийн хуулиуд энгийнээр ажилладаг энгийн дэлхий дээр амьдардаг гэж үзнэ үү. Иймээс магадгүй бид дахин нэг тоосго нэмж тавихад тухайн барилга нь нуран унаж болох юм. Вася дор хаяж нэг ширхэг тоосго барилгын тэнцвэрийг алдагдуулан нуран унах хүртэл барилгын орой дээр тоосгонуудаа нэг нэгээр нь тасралтгүй тавьсаар байх юм. Хэрэв барилга нуран унавал Вася бухимдах бөгөөд уг барилгын ажлаа зогсооно. Тэгвэл хамгийн бат бөх барилга дахь тоосгоны тоог хэвлэнэ үү. Өөрөөр хэлбэл 1-ээс $m$-ын хооронд байх бүхэл тоо $k$ бүрийн хувьд 1, 2, ..., $k$ гэсэн дугаартай тоосгонуудаас тогтох бүх барилгууд нь бат бөх байх хамгийн их $m$-ын утгыг хэвлэнэ үү.

Оролт

Эхний мөрөнд тоосгоны тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 100$) өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд 4-н тоо $x_{i, 1}, y_{i, 1}, x_{i, 2}, y_{i, 2}$ ($x_{i, 1} ≠ x_{i, 2}, |x_{i, 1} - x_{i, 2}| = |y_{i, 1} - y_{i, 2}|$) өгөгдөх ба эдгээр нь $i$ дугаартай тоосгоны суурийн эсрэг булангуудын координатуудыг илэрхийлнэ. Координатууд нь бүхэл тоонууд байх бөгөөд тэдгээрийн абсолют утгууд нь $50$-аас хэтрэхгүй байна.

Тоосгонууд нь Вася-ын тэдгээрийг тавьсан дарааллаар өгөгдөнө. Мөн $i ≥ 2$ байх бүх $i$-ын хувьд $i - 1$ дугаартай тоосгоны дээд хэсэг болон $i$ дугаартай тоосгоны доод хэсгийн огтлолцолд үүсэх хэсгийн талбай нь 0-ээс эрс их байна.

Гаралт

Хамгийн бат бөх барилга дахь тоосгоны тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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