D. Бабая ба Төрсөн өдрийн бялуу

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

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

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

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

Таны мэдэж байгаачлан төрсөн өдрийн үдэшлэг бүр бялуутай байдаг! Энэ удаа Бабая маш өвөрмөц төрсөн өдрийн үдэшлэгний бялуу хийхээр бэлдэх гэж байна.

Энгийн бялуу нь тодорхой радиус болон өндөртэй цилиндр байдаг. Уг энгийн бялууны эзэлхүүн нь харгалзах цилиндрийн эзэлхүүнтэй тэнцүү. Бабаяд $n$ ширхэг энгийн бялуу байгаа ба тэр уг бялуунуудыг дээр дээр нь давхарлах замаар өвөрмөц бялуугаа хийх гэж байна.

Гэсэн хэдий ч энд гал тогооны хэд хэдэн хязгаарлалтууд байна. Бялуунууд нь дараах замаар дугаарлагдах ба энэ нь $i$ дугаартай бялуу зөвхөн ширээн дээр эсвэл $j < i$ байх $j$ бялуун дээр л тавигдаж болно. Үүгээр ч барахгүй Бабая найзууддаа сэтгэгдэл төрүүлэхийн тулд $i$ бялууны эзэлхүүн $j$ бялууны эзэлхүүнээс их үед л $i$ бялууг $j$ бялууны дээр тавина.

Бабая хамгийн их эзэлхүүнтэй бялууг бэлтгэхийг хүсэж байна. Түүнд энэ утгыг олоход туслана уу.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000)$ байх ба Бабаяд байгаа бялууны тоо юм.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $r_{i}$ ба $h_{i}$ ($1 ≤ r_{i}, h_{i} ≤ 10 000$) байх ба $i$-р бялууны радиус болон өндөр юм.

Гаралт

Бабая-н хийж чадах бялууны хамгийн их эзэлхүүнийг хэвлэ. Хэрвээ таны хариуны үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-ээс хэтрээгүй бол зөв гэж үзнэ.

Өөрөөр хэлбэл: Таны хариултыг $a$ гэж үзвэл, шалгагчийн хариу $b$. Шалгагч программ таны хариултыг хэрвээ . бол зөв гэж авч үзнэ.

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

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

Оролт
2
100 30
40 10
Гаралт
942477.796077000
Оролт
4
1 1
9 7
1 4
10 7
Гаралт
3983.539484752

Тэмдэглэл

Эхний жишээн дээр хамгийн тохиромжтой зам бол $1$ дугаартай бялууг сонгох юм.

Хоёр дахь жишээн дээр хамгийн их эзэлхүүнтэй бялууг гаргаж авах зам бол $1$, $2$, $4$ дугаартай бялуунуудыг ашиглах явдал юм.

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