B. Групп зураг 2 (онлайн толин хувилбар)

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

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

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

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

Олон жилийн дараа үдэшлэг дээр $n$ найзууд дахин уулзалдав. Тэдний сүүлийн уулзалтаас хойш технологийн хөгжил өсөн нэмэгдэж зураг авах цагаа тохируулдаг камер бий болсон байна. Тиймээс найзуудын нэг нь заавал камер барьж зогсох шаардлагагүй бүгд хамтдаа зургаа авахуулах боломжтой юм.

Энгийнээр хэлбэл зураг авах үйл явцыг дараах байдлаар тодорхойлж болно. Зураг дээр гарч буй найз бүр зургийн тэгш өнцөгт пикселийг эзэлнэ: тэдгээрийн $i$-р найз нь $w_{i}$ өргөнтэй, $h_{i}$ өндөртэй тэгш өнцөгт пиксел эзэлнэ. Гэхдээ зураг дээр хүн бүр хэвтэж зургаа авахуулах боломжтой учраас $h_{i}$ өргөнтэй, $w_{i}$ өндөртэй тэгш өнцөгт пиксел эзэлж болно.

Зургаа авахуулж буй бүх найзуудыг оролцуулсан зургийн пикселийн хэмжээ нь $W × H$ байна. Энд $W$ нь зургаа авахуулж буй бүх найзуудын өргөний нийлбэр бол $H$ нь зургаа авахуулж буй бүх найзуудын хамгийн өндөр нь юм. Хэрвээ тэдгээрийн $n/2$-оос ихгүй найз нь газарт хэвтэх бол найзууд өөрсдийн авч чадах зургийн хамгийн бага талбайг тодорхойлохыг хүсэж байна. (Хэрвээ $n/2$-оос олон найз хамтдаа газарт хэвтвэл онцгүй харагдана, тийм биш гэж үү?)

Энэ зорилгодоо хүрэхэд нь туслаарай.

Оролт

Эхний мөрөнд найзуудын тоо болох $n$ ($1 ≤ n ≤ 1000$) бүхэл тоо байна.

Дараа нь $n$ ширхэг мөр байна: $i$-р мөрөнд $i$-р найзын талаарх мэдээлэл байна. Энэ мөрөнд $w_{i}, h_{i}$ ($1 ≤ w_{i}, h_{i} ≤ 1000$) хоёр бүхэл тоо байх ба эдгээр нь харгалзан тэгш өнцөгт пикселийн өргөн болон өндөр юм.

Гаралт

$n/2$-оос ихгүй найз нь газарт хэвтэх байдлаар найзуудын авч чадах зургийн хамгийн бага талбай болох нэг бүхэл тоо хэвлэнэ.

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

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

Оролт
3
10 1
20 2
30 3
Гаралт
180
Оролт
3
3 1
2 2
4 3
Гаралт
21
Оролт
1
5 10
Гаралт
50
Сэтгэгдлүүдийг ачааллаж байна...