E. Дууны жагсаалт

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

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

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

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

Манаогийн найзууд түүнд байнга дуу явуулдаг. Тэрээр явуулсан дуунуудыг ирсэн дариуд нь сонсдоггүй. Харин тэдгээр дуунуудыг багцлан дууны жагсаалт болгодог. Манао дуу сонсмоор санагдсан үедээ дууны жагсаалтыг эхнээс нь сонсдог.

Мэдээж эдгээр дуунууд дунд Манаод таалагдахгүй дуунууд байдаг. Тиймээс ирсэн дуунуудаас илүү их таашаал авахын тулд дараах дуу сонсох дарааллыг үүсгэжээ:

  • Хэрвээ Манаогийн сонссон дуу түүнд таалагдвал энэ дууг санаж дараагийн сонсоогүй дууг сонсдог.
  • Хэрвээ Манаогийн сонссон дуу түүнд таалагдахгүй бол энэ дуу хүртэл бүх таалагдсан буюу санасан дуунуудаа дахиж сонсон дараагийн сонсоогүй дууг сонсдог.

Жишээ нь, дууны жагсаалтанд $A$, $B$, $C$, $D$ (энэ дарааллаар сонсоно) гэсэн $4$-н дуу байна. Түүнд таалагдах дуунууд нь $A$ болон $C$ бол дууг сонсох дараалал дараах байдлаар байх болно:

  1. Манао $A$-г сонсоно, түүнд таалагдаж энэ дууг санана.
  2. Манао $B$-г сонсоно, түүнд таалагдахгүй, тиймээс тэрээр дахиад $A$-г сонсоно.
  3. Манао $C$-г сонсоно, түүнд таалагдаж үүнийг бас санах болно.
  4. Манао $D$-г сонсоно, түүнд таалагдахгүй учир тэрээр дахин $A$ болон $C$-г сонсоно.

Тэгэхлээр Манао $A$ дууг $3$-н удаа, $С$ дууг $2$ удаа, $B$ болон $D$ дууг тус тус $1$ удаа сонссон байх болно. Хэрвээ Манаод нэг дуу таалагдсан бол тэрээр дараагийн удаа сонсоход энэ дуунд дургүй болох боломжгүй.

Манаод $n$ ширхэг дуу ирсэн: $i$ дэхь дуу $l_{i}$ секунд урттай бөгөөд Манаод таалагдах магадлал $p_{i}$ байна. Дуунууд дууны жагсаалтанд ямар ч дараалалтайгаар орж болно. Тиймээс Манаогийн дууны жагсаалтыг сонсох нийт хугацаа хамгийн их байхаар дараалалтайгаар дуунуудыг сонсоход хэр удаан сонсох вэ? гэдгийг мэдэхийг хүсжээ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 50000$) өгөгдөнө. Дараагийн $n$ ширхэг мөрний $i$ дэхь мөрөнд хоёр бүхэл тоо буюу $l_{i}$ болон $p_{i}$ ($15 ≤ l_{i} ≤ 1000$, $0 ≤ p_{i} ≤ 100$) өгөгдөнө. Эдгээр нь $i$ дууны хэмжээг секундээр өгсөн тоо болон Манаод энэ дуу таалагдах магадлалыг хувиар өгсөн байна.

Гаралт

Нэг мөрөнд нэг ширхэг бодит тоо хэвлэнэ. Энэ нь боломжит бүх дарааллын хувилбаруудаас хамгийн их хугацаа нь юм. Хариуны үнэмлэхүй болон харьцангуй алдаа $10^{-9}$-ийг хэтрэхгүй бол тооцно.

Орчуулсан: Энхлут

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

Оролт
3
150 20
150 50
100 50
Гаралт
537.500000000
Оролт
4
300 0
300 50
240 50
360 80
Гаралт
2121.000000000

Тэмдэглэл

Эхний тестэнд Манао өгөгдсөн дарааллаар дуунуудыг сонсвол нийт хугацаа $467.5$ секунд болно. Хамгийн их хугацааг олохын тулд эхний дууг дууны жагсаалтын хамгийн сүүлд тавина.

Хоёр дахь тестэнд $360$ секунд урттай дуу хамгийн эхэнд болон $300$ секунд урттай Манаогийн дургүй дууг хамгийн сүүлд тавих юм.

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