19882번 - Печать 다국어

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

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

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

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

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

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

Первокурсник Макс только что решил с головой погрузиться в учебу. К завтрашнему семинару по мифологии ему необходимо подготовить доклад в $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 страницы, что больше требуемых двух.