Бодолт илгээх | Бүх бодолтууд | Шилдэг бодолтууд | Жагсаалт руу буцах |
A2410B - Принтерийн хор |
Оюутан Төгөлдөр бие даалтаа хэвлэхээр шийджээ. Түүний бие даалт k хуудастай. Гэтэл
түүний принтерийн хор дууссан тул шинэ хор худалдаж авах шаардлагатай болов. Дэлгүүрт
түүний принтерт таарах n төрлийн хор байв. Худалдагч түүнд хорнуудын үнэ болон хэвлэх
хуудасны тоог нь хэлсэн.
i-р төрлийн хор нь ci төгрөгийн үнэтэй бөгөөд pi хуудас хэвлэх боломжтой. Дэлгүүрт бүх
төрлийн хор хязгааргүй тоогоор хадгалагдаж байгаа.
Төгөлдөр аль болох хямдхан бөгөөд бие даалтыг хэвлэхэд яг таарсан хор худалдаж авахыг
хүсэж байгаа юм. Өөрөөр хэлбэл яг k хуудас хэвлэхэд хүрэлцэх, хамгийн бага нийт өртөгтэй
хорнуудыг худалдаж авмаар байна.
Оролт:
Оролтын эхний мөрөнд дэлгүүрт байнгаа хорны төрлийн тоо n ба Төгөлдөрийн бие даалтын
хуудасны тоо k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 109) гэсэн хоёр бүхэл тоо өгөгдөнө.
Дараа нь n мөр байна. Тэдгээрийн i-р мөрөнд i-р төрлийн хорны үнэ, түүгээр хэвлэх
хуудасны тоо болох ci ба pi (1 ≤ ci, pi ≤ 200) тоонууд өгөгдөнө.
Гаралт: Гаралтад Төгөлдөр авч болох яг k хуудас хэвлэхэд хүрэлцэх хорнуудын хамгийн бага нийт
өртөг болох нэг бүхэл тоог гаргана. Хэрэв шийдэл байхгүй бол −1 гаргаарай.
Жишээ:
Оролт | Гаралт |
4 5 5 5 2 3 5 10 1 1 |
4 |
1 2 1 3 |
-1 |
Эхний жишээнд Төгөлдөр хоёр дахь төрлийн нэг хор, дөрөв дэх төрлийн хоёр хор худалдаж
авах ёстой. 4 төгрөг төлснөөр Төгөлдөр яг 5 хуудас хэвлэх юм.
Хоёр дахь жишээнд зөвхөн нэг төрлийн хор байгаа бөгөөд үүнийг худалдаж авснаар
Төгөлдөр 3 хуудас хэвлэх боломжтой бөгөөд энэ нь шаардлагатай хоёр хуудаснаас илүү
гарч байгаа учир шийдгүй юм.
Нэмсэн: | munkhbat |
Огноо: | 2024-01-29 |
Хугацааны хязгаарлалт: | 1s |
Эх кодын хэмжээний хязгаарлалт: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Програмчлалын хэлүүд: | Бүгд дараах хэлүүдээс бусад: NCSHARP JULIA PYPY3 |