Uzb Eng

0029. Pechat
: 2 c
: 64

Birinchi kursda oqiyotgan Behzod oqishga judayam kirishib ketdi. Ertaga boladigan siminar uchun mifologiya boyicha k varaqli maruza tayyorlashi kerak. Behzod mifologiyani yaxshi koradi, shuning uchun maruzasi tayyor boldi. Faqatgina uni printerdan chiqarish qoldi.
Afsuski, yotoqxonadagi printerlarning barchasini kartridji tugab qolibdi. Endi Behzod yangi kartridj sotib olishi lozim. Magazinda n turdagi kartridjlar bor ekan. Sotuvchi Behzodga kartridjlar asosan ikki xil parametrga ega ekanligini tushuntirdi, yani kartridj narxi va pechat qiladigan varaqlar soni.
Malim boldiki, i-chi turdagi kartridj narxi ci va varaqlar soni pi ekan. Magazinda har bir turdagi kartridjlardan chegaralanmagan miqdorda mavjud.
Behzod oddiy talaba bolsa, shuning uchun u shunday arzon kartridjni sotib olishi kerakki, uning maruzasini pechat qilishga etsin. Ikkinchi tomondan esa Behzod judayam xasis. Agarda Behzod maruzasini pechat qilgandan song atigi bitta varaqni pechat qilishi mumkin bolgan resurs kartridjda qolsa, yotoqxonadagilar uning oldiga hujjatlarini pechat qilishga olib kelishlarini biladi.
Shuning uchun, Behzod narxi eng minimal bolgan va k varaqni pechat qilishga teng bolgan kartridgni sotib olishni xoxlaydi.
Behzodga minimal summaga kardtridj olishga va xasislik qilmasligiga yordam bering.
Birinchi misolda Behzod bitta ikkinchi turli va ikkita tortinchi turli kartridj sorib olishi lozim. Ular ychun 4 som tolaydi. Behzod 5 varaqni pechat qilsh imkoniga ega boladi.
Ikkinchi misolda esa Behzod faqatgina bitta kartridjni sotib olib uch varqani pechat qilishi mumkin. Bu esa talab qilinga ikkita varaqdan kop.

:
Birinchi satrda ikkita n va k sonlari berilgan (1 < < 100 000, 1 < k < 109). Mos ravishda magazindagi kartridj turlari va Behzodning maruzasining varaqlar soni. Keyingi n ta satrda esa har bir kartridjning narxi va maksimal pechat qilshi mumkin bolgan varaqlar soni berilgan. Masalan, i-chi kardtidjniki Ci va pi (1 < Ci,pi < 200) .

:
k varaqni chiqarishi uchun Behzod sarflashi mumkin bolgan eng minimal summani chiqaring. Agarda bunday yechim mavjud bolmasa -1 (minus bir) ni chiqaring.

4 5
5 5
2 3
5 10
1 1
1 2
1 3
4





-1
:
: XIX - 2011


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.