Рабочее место участника

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

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

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

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

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

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

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

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

4 5
5 5
2 3
5 10
1 1

4

1 2
1 3

-1

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

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