Задача №113679. Печать
Первокурсник Макс только что решил с головой погрузиться в учебу. К завтрашнему семинару по мифологии ему необходимо подготовить доклад в \(k\) страниц. Макс любит мифологию, так что доклад уже готов, осталось только его распечатать.
К сожалению, во всех имеющихся в общежитии принтерах закончились картриджи, и теперь Максу придется купить новые картриджи для печати доклада. В магазине обнаружилось \(n\) типов картриджей. Продавец объяснил Максу, что картридж имеет два основных параметра — стоимость и количество страниц, на печать которых его хватает.
Выяснилось, что картридж \(i\)-го типа стоит \(c_i\) рублей и может напечатать \(p_i\) страниц. В магазине есть в наличии неограниченное количество картриджей каждого типа.
Макс — бедный студент, поэтому он хочет как можно дешевле приобрести картриджи, которых вместе бы хватило для печати доклада. С другой стороны, Макс очень жадный. Он знает, что если после печати доклада у него останется ресурс хотя бы на одну страницу, еще год все в общежитии будут ходить к нему распечатывать документы.
Поэтому Макс хочет купить картриджей с минимальной суммарной стоимостью, которых достаточно для печати ровно \(k\) страниц.
Помогите Максу — посчитайте минимальную сумму, на которую ему придется раскошелиться.
В первой строке входного файла содержатся числа \(n\) — количество типов картриджей в ассортименте магазина и \(k\) — количество страниц в докладе Макса (\(1 \le n \le 100 000, \ 1 \le k \le 10^9\) ). Далее следуют \(n\) строк, \(i\)-я из них содержит числа \(c_i\) и \(p_i \ (1 \le c_i , \ p_i \le 200\)) — стоимость картриджа \(i\)-го типа и число страниц, которое можно распечатать с его помощью, соответственно.
Выходной файл должен содержать одно число — минимальное количество денег, которое придется потратить Максу, чтобы распечатать ровно \(k\) страниц. Если решения не существует, выведите в выходной файл \(−1\).
В первом примере Максу следует купить один картридж второго типа и два картриджа четвертого типа. Заплатив 4 рубля, Макс получит возможность напечатать ровно 5 страниц.
Во втором примере есть лишь один тип картриджей, купив его Макс получит возможность напечатать 3 страницы, что больше требуемых двух.
4 5 5 5 2 3 5 10 1 1
4
1 2 1 3
-1