Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Закупка дров
Небезызвестный дачник Леонид Юрьевич переключился с проектирования водопровода на подготовку к отопительному сезону. 

Будучи доктором технических наук, Леонид Юрьевич подсчитал, что для отопления своего дачного участка в течение зимы необходимо затратить H кг дров. При этом он знает N поставщиков, каждый из которых продает дрова охапками по Pi кг дров в каждой и стоимостью Ci

Естественно, Леонид Юрьевич хочет как можно выгоднее подготовиться к отопительному сезону. В связи с этим он хочет потратить наименьшее количество денег и при этом купить не менее, чем H кг дров. Заметим, что каждый из поставщиков имеет бесконечное число охапок дров и продает их только охапками и никак иначе. 

Помогите Леониду Юрьевичу решить его непростую задачу.
Входные данные:

Первая строка файла содержит два натуральных числа N (1 ≤ N ≤ 100) и H (1 ≤ H ≤ 50000) – количество поставщиков и необходимая масса дров для отопительного сезона соответственно.

Далее следует N строк, каждая из которых содержит описание поставщиков дров: два числа Pi и Ci (1 ≤ i N) – масса дров в охапке и стоимость всей охапки.

Выходные данные:
В выходной файл требуется единственное число – минимальное количество денежных средств, которое потребуется Леониду Юрьевичу, чтобы купить не менее H кг дров.

Примеры:
input.txt output.txt
1 2 15
3 2
5 3
9

Сложность задачи: 25%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
В приведенном примере Леонид Юрьевич должен купить три охапки дров у второго поставщика.
Показать обсуждение


На сайте гостей 18, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]