0222. Печать

Input file name:	printing.in
Output file name:	printing.out
Time limit:	2 s
Memory limit:	256 megabytes

Первокурсник Макс только что решил с головой погрузиться в учебу. К завтрашнему семинару по мифологии ему необходимо подготовить доклад в k страниц. Макс любит мифологию, так что доклад уже готов, осталось только его распечатать.

К сожалению, во всех имеющихся в общежитии принтерах закончились картриджи, и теперь Максу придется купить новые картриджи для печати доклада. В магазине обнаружилось n типов картриджей. Продавец объяснил Максу, что картридж имеет два основных параметра – стоимость и количество страниц, на печать которых его хватает.

Выяснилось, что картридж i-го типа стоит c_i рублей и может напечатать p_i страниц. В магазине есть в наличии неограниченное количество картриджей каждого типа.

Макс – бедный студент, поэтому он хочет как можно дешевле приобрести картриджи, которых вместе бы хватило для печати доклада. С другой стороны, Макс очень жадный. Он знает, что если после печати доклада у него останется ресурс хотя бы на одну страницу, еще год все в общежитии будут ходить к нему распечатывать документы.

Поэтому Макс хочет купить картриджей с минимальной суммарной стоимостью, которых достаточно для печати ровно k страниц.

Помогите Максу – посчитайте минимальную сумму, на которую ему придется раскошелиться.

Формат входного файла

В первой строке входного файла содержатся числа n – количество типов картриджей в ассортименте магазина и k – количество страниц в докладе Макса (1 ≤ n ≤ 100,000, 1 ≤ k ≤ 10⁹). Далее следуют n строк, i-я из них содержит числа c_i и p_i (1 ≤ c_i, p_i ≤ 200) – стоимость картриджа i-го типа и число страниц, которое можно распечатать с его помощью, соответственно.

Формат выходного файла

Выходной файл должен содержать одно число – минимальное количество денег, которое придется потратить Максу, чтобы распечатать ровно k страниц. Если решения не существует, выведите в выходной файл -1.

Пример:

В первом примере Максу следует купить один картридж второго типа и два картриджа четвертого типа. Заплатив 4 рубля, Макс получит возможность напечатать ровно 5 страниц. Во втором примере есть лишь один тип картриджей, купив его Макс получит возможность напечатать 3 страницы, что больше требуемых двух.

printing.in	printing.out
4 5 5 5 2 3 5 10 1 1	4
1 2 1 3	-1

Source: Командное школьное первенство Республики Карелия по программированию, 30 октября 2011.

Discuss       Submit a solution



Printable version