HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Непрерывный рюкзак

Section problems

• Наибольшая возрастающая подпос...
• Наибольшая общая подпоследова...
• Наибольший общий делитель
• Наилучший участок
• Наилучший участок
• Наилучший участок
• Наименьшее число
• Необычный календарь
• Непрерывный рюкзак
• Несчастливые дни
• Несчастливые дни
• Нормализация пути
• Обмены в Heapify
• Общие замечания
• Одного ли цвета?
• Ой-ай!
• 1

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Непрерывный рюкзак
Непрерывный рюкзак
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Имеется N куч драгоценного песка. i-я куча содержит Wi килограммов песка, стоимость песка из i-й кучи равна Pi рублей за килограмм.

У вас есть рюкзак, в котором можно унести песок общей массой не более M килограммов. Вы хотите заполнить рюкзак так, чтобы общая стоимость находящегося в нём песка была максимальной.

Определите, как следует заполнить рюкзак песком.

Входные данные

Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 104) — соответственно количество куч песка и максимальную вместимость рюкзака в килограммах.

Следующие N строк описывают кучи песка. Каждая из них содержит целые числа Wi и Pi (1 ≤ Wi, Pi ≤ 104) — соответственно общую массу песка из i-й кучи в килограммах и стоимость одного килограмма песка из i-й кучи в рублях.

Выходные данные

Выведите одно целое число — максимальную суммарную стоимость песка, которым можно заполнить рюкзак, выраженную в рублях.

Примеры

Входные данные
5 10
7 5
8 10
4 9
4 5
3 6
Выходные данные
98
Входные данные
7 20
4 8
5 5
5 8
6 10
4 18
5 11
7 7
Выходные данные
227
Входные данные
6 11
1 18
7 10
7 7
8 6
7 10
8 5
Выходные данные
118
Для отправки решений необходимо выполнить вход.

www.contester.ru