B. Энэ дууг нэрлэ

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

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

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

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

Та рок хамтлаг AC/PE хамтлагийн агуу шүтэн бишрэгч. Петер дараах тоглоомыг сурсан ба эхэлсэн: Тэр группд байгаа $n$ дууны жагсаалтын эхний дууг тоглох ба та дууны нэрийг олох ёстой. Таныг дууны нэрийг хэлмэгц дараа Петер дараагийн дууг тоглоно гээд үргэлжилнэ.

AC/PE-н $i$-р дуу өөрийн танигдах магадлал $p_{i}$ утгатай. Энэ нь хэрвээ та дууг хараахан таниагүй бол та дууг яг нэг секундын турш сонсох ба та дууг $p_{i}$ магадлалтайгаар таах ба нэрийг нь хэлнэ. Бусад тохиолдолд үргэлжлүүлэн үүнийг сонсоно. Та дуу явж эхэлсэн мөчөөс хойш бүхэл тоон секунд өнгөрсөн үед л таах гэж оролдож чадна гэдгийг сана.

AC/PE-н бүх дуунуудын түрлэгийн эхний үгүүд нь дууны нэртэй ижил байдаг ба та $i$-р дууны эхний $t_{i}$ секундыг сонссон үед түрлэг эхлэх ба та шууд дууны нэрийг гарцаагүй хэлнэ.

Жишээлбэл Highway To Red дуунд түрлэг нэлээд хойно дуугарадаг боловч дууны нэр өндөр танигдах магадлалтай. Back In Blue дуунд нөгөө талаас нэрний үгүүд дууны эхэнд сонсогддог боловч эдгээр үгүүдийг сонсохоос нааш нэрлэх хэцүү. Та энэ хоёр дууг эхний хэдхэн секундын хугацаанд нэрлэж чадна.

Хэрвээ тоглоом $T$ секунд үргэлжлэх бол та таниж чадах дуунуудын дундаж тоог ол (та $T$ дахь секундэд сүүлийн таалтаа хийж чадах ба үүний дараа тоглоом дуусна).

Хэрвээ бүх дуунууд $T$ секундээс хурдан хугацаанд таагдвал тоглоом хамгийн сүүлийн дуу таагдсаны дараа зогсоно.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан $n$ ба $T$ ($1 ≤ n ≤ 5000$, $1 ≤ T ≤ 5000$) тоонууд байна. Дараагийн $n$ мөрөнд $p_{i}$ ба $t_{i}$ ($0 ≤ p_{i} ≤ 100$, $1 ≤ t_{i} ≤ T$) тоонуудын хосууд байна. Дуунууд Петягийн жагсаалттай адил дарааллаар өгөгдөнө.

Гаралт

Нэг ширхэг тоо хэвлэх ба энэ нь та $T$ секунддэд тааж чадах дуунуудын дундаж тоо байна. Таны хариултын үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-с ихгүй байвал таны хариулт зөвд тооцогдоно.

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

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

Оролт
2 2
50 2
10 1
Гаралт
1.500000000
Оролт
2 2
0 2
100 2
Гаралт
1.000000000
Оролт
3 3
50 3
50 2
25 2
Гаралт
1.687500000
Оролт
2 2
0 2
0 2
Гаралт
1.000000000
Сэтгэгдлүүдийг ачааллаж байна...