E. Бэлэгнүүд

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

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

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

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

Эрт урьдын цагт хөгшин эр эхнэртэйгээ уудам цэнхэр тэнгисийн ойр амьдардаг байж гэнэ. Нэгэн өдөр хөгшин эр загасчлахаар яваад жинхэнэ алтан загас барьжээ. Гэтэл загас "Ай, хөгшин загасчин минь! Намайг тэнгист минь эргүүлэн тавиач дээ. Оронд нь таны хүссэн $n$ бэлгийг танд өгье!" гэж хэлж гэнэ. Тэгээд загас хөгшин эрд бэлэгний нэр болон үнийг бичсэн жагсаалт өгчээ. Жагсаалт дээрх зарим бэлэг ижил нэртэй ч, өөр үнэтэй байв. Гэхдээ ижил нэртэй, ижил үнэтэй бэлэг байсангүй. Гэвч өөр нэртэй, ижил үнэтэй бэлэг жагсаалтанд агуулагджээ. Хөгшин эр жагсаалтан дээрх зүйлсээс $n$ нэр хэлж болно. Жагсаалтанд энэхүү нэртэй ижил нэртэй $p$ тооны илэрц гарвал, хөгшин эр энэхүү нэрийг $p$-ээс олон удаа хэлж болохгүй.

Хөгшин эр адилхан нэртэй $s$ тооны бэлэг хүсвэл загас жагсаалтнаас ижил нэртэй, ялгаатай үнэтэй $s$ тооны бэлгийг таамгаар (өөрөөр хэлбэл, бүх сонголтон дундаас ижил магадлалаар) сонгоно. Хөгшин эр өөрийн шунахай эхнэрт таалагдахыг хүсдэг тул тэрээр хамгийн үнэтэй $n$ бэлгийг авах замаар $n$ нэр сонгохыг хүсчээ. Даанч тэр тийм ч ухаалаг загасчин биш. Тиймээс хэд хэдэн боломж байвал тэр нэгийг нь таамгаар сонгоно.

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

Оролт

Эхний мөр нь хөгшин эрийн хүслийн тоо болон алтан загасны жагсаалтанд байгаа ялгаатай нэрсийн тоог харуулах зайгаар тусгаарлагдсан $n$ ба $m$ ($1≤n, m≤1000$) 2 бүхэл тоог агуулна. Дараагийн $m$ мөрийн хувьд: $i$-р мөр нь $i$-р нэртэй бэлэгний ялгаатай үнийн тоог харуулах $k_{i}$ $(k_{i}>0)$ бүхэл тоо, түүний дараа бэлэгний үнүүдийг харуулах, зайгаар тусгаарлагдсан $k_{i}$ ширхэг $c_{ij}$ ($1≤c_{ij}≤10^{9}$) бүхэл тоонуудыг агуулна.

Энд, $k_{i}$ тоонуудын нийлбэр 1000-аас хэтрэхгүй. Мөн $n$ тоо нь бэлэгний тооноос ихгүй байна.

Гаралт

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

Орчуулсан: Солонго

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

Оролт
3 1
3 10 20 30
Гаралт
1.000000000
Оролт
3 2
1 40
4 10 20 30 40
Гаралт
0.166666667
Сэтгэгдлүүдийг ачааллаж байна...