06/04/2025 22:10:43

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1690. Печать

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

$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$ .

Пример ввода 1

Пример вывода 1

Пример ввода 2

1 2
1 3

Пример вывода 2

-1

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

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

Источник: XIX Командный чемпионат школьников Санкт-Петербурга по программированию, 2011

30/10/2011	Региональные отборочные командные соревнования для школьников (E)
05/11/2011	Занятие 5 (E)