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

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

Наследство
Долгожитель Мохаммед решил определить, за сколько недель ему удастся достичь счастья. Прожил он долгую и насыщенную жизнь и сейчас вспомнил, что в детстве ему было предсказано, что счастье его наступит тогда и только тогда, когда он передаст всё наследство своим детям. У Мохаммеда имеется N различных видов монет, каждый из видов имеет определенное достоинство Vi. И для того, чтобы подольше расставаться со своим богатством Мохаммед решил выдавать каждую неделю не менее C денежных единиц. Сколько недель потребуется Мохаммеду, чтобы достичь счастья?
Входные данные:
Первая строка файла содержит два натуральных числа N (1 ≤ N ≤ 20) и C (1 ≤ C ≤ 100000000) – количество видов монет и сумма, отдаваемая в неделю соответственно. 
 Следующие N строк содержат по два натуральных числа Vi, Bi (1 ≤ Vi ≤ 100000000, 1 ≤ Bi ≤ 1000000, 1≤ i ≤ N) – достоинство и количество монет соответственно.
Выходные данные:
В выходной файл требуется вывести единственное число – количество недель, через которое наступит счастье.

Пример:
Мохаммед отдаст одну монету достоинством 10 в первую неделю, затем он будет платить по две монеты достоинством 5 в течение 10 недель, а затем будет платить по одной монете достоинством 1 и одной монете достоинством 5 в течение 100 недель

Примеры:
input.txt output.txt
1 3 6
10 1
1 100
5 120
111

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



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


Показать обсуждение


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