B. Давхаргатай бялуу

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

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

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

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

Даша бас том амттай давхаргатай бялуу хийхээр шийдсэн. Үүнийг хийхийн тулд тэр дэлгүүр явсан ба $n$ тэгш өнцөгт бялууны давхарга авсан. $i$-р давхарганы урт болон өргөн нь харгалзан $a_{i}$ ба $b_{i}$ байсан ба давхарга болгоны өндөр нэгтэй тэнцүү байсан.

Даша хоолны номон дээрээс бялуу нь ижил хэмжээтэй бялууны давхаргануудаар бүтээсэн тэгш өнцөгт параллелепипед хэлбэртэй байх ёстой гэдгийг сурсан.

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

Даша бялуугаа ижил хэмжээтэй бялууны давхаргуудын стэк маягаар баригдаасай гэж хүсч байна. Үр дүнд нь гарах бялууны давхарга бүр зөвхөн нэг бялууны давхарга байна (анхны эсвэл анхны бялууны давхаргаас зүсч авсан).

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

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ $(1 ≤ n ≤ 4000)$ байх ба Дашагийн хэрэглэж болох бялууны давхаргуудын тоо байна.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ 10^{6})$ байх ба харгалзан $i$-р бялууны давхаргын урт ба өргөн байна.

Гаралт

Гаралтын эхний мөрөнд өгөгдсөн давхаргуудыг ашиглан хийж чадах бялууны хамгийн их эзэлхүүн байна.

Гаралтын хоёр дахь мөрөнд бялууны урт ба өргөн байна. Хэрвээ хэд хэдэн боломжит хамгийн их эзэлхүүнтэй шийдэл байвал алийг нь ч хэвлэж болно.

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

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

Оролт
5
5 12
1 1
4 6
6 4
4 6
Гаралт
96
6 4
Оролт
2
100001 900000
900001 100000
Гаралт
180000000000
900000 100000

Тэмдэглэл

Эхний жишээн дээр Даша хоёр дахь бялууны давхаргыг ашиглахгүй. Тэр эхний бялууны давхаргаас $4 × 6$ хэмжээтэй тэгш өнцөгт зүсэж авах ба бусад давхаргуудыг хэвээр нь ашиглана.

Хоёр дахь жишээн дээр Даша хоёр бялууны давхаргуудаас жаахан зүсч хаяна.

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